# Solutions to Some Optional Problems

Exercise 1: The formulation is:

Exercise 2: Let be a 0,1 variable which equals 1 if route j is used, 0 otherwise. Then the vehicle routing problem can be formulated as a set covering problem:

Exercise 3: Let starting time of operation j.

Then the formulation is:

The first set of constraints are the precedence constraints and the last two sets are the noninterference constraints.

Exercise 4: First we solve the problem as a linear program with LINDO. The solution is , . Rounding it yields , which fails to satisfy the constraint .

In fact, the only feasible integer solution is

and it cannot be obtained by simple rounding.

Exercise 5: The enumeration tree is given in Figure 9.

Figure 9: Enumeration tree

Three optimum integer solutions were found, namely

each with value z=5.

Exercise 6

From the enumeration tree of Exercise 5, we see that only one branching is necessary since both subproblems and are inactive by reason of integrality. The better solution is with value .

Exercise 7

```MAX 4 X1 + 7 X2 + 6 X3 + 5 X4 + 4 X5
SUBJECT TO
2) 5 X1 + 8 X2 + 3 X3 + 2 X4 + 7 X5 <= 112
3) X1 + 8 X2 + 6 X3 + 5 X4 + 4 X5 <= 109
END
GIN 5

ENUMERATION COMPLETE. BRANCHES= 6 PIVOTS= 20

OBJECTIVE FUNCTION VALUE  151.000

VARIABLE      VALUE      REDUCED COST
X1      14.000           -4.000
X2        .000           -7.000
X3        .000           -6.000
X4      19.000           -5.000
X5        .000           -4.000```

Exercise 8

Since does not satisfy the knapsack constraint , it follows that must hold for all solutions of the knapsack problem.

Similarly for .

```MAX 8 X1 + 11 X2 + 6 X3 + 4 X4
SUBJECT TO
2) 5 X1 + 7 X2 + 4 X3 + 3 X4  <= 14
3) X1 +  X2 +  X3 <= 2
3) X1 +  X2 +  X4 <= 2
END
SUB X1 1
SUB X2 1
SUB X3 1
SUB X4 1

OBJECTIVE FUNCTION VALUE  21.000

VARIABLE      VALUE      REDUCED COST
X1        .000            0.000
X2       1.000           -3.000
X3       1.000           -2.000
X4       1.000            0.000```

Exercise 9.

(a) Nearest Neighbor starting from city 1 yields the tour

1 - 4 - 8 - 9 - 10 - 13 - 14 - 11 - 12 - 15 - 7 - 5 - 6 - 2 - 3 - 1

of length 89.

Applying 2-opt, we get the following improvements: replace 1-3 and 2-6 by 1-2 and 3-6 for a gain of 6. The new tour is

1 - 2 - 3 - 6 - 5 - 7 - 15 - 12 - 11 - 14 - 13 - 10 - 9 - 8 - 4 - 1

Replace 3-6 and 5-7 by 3-5 and 6-7 for a gain of 2. The new tour

1 - 2 - 3 - 5 - 6 - 7 - 15 - 12 - 11 - 14 - 13 - 10 - 9 - 8 - 4 - 1

has lenth 81.

(b) We start Nearest Insertion with the tour 5 - 6 - 5 of length 6.

Then we insert city 7 at a cost of 4+5-3=6 (note that there is a tie. We could have inserted city 9 instead). The new tour is 5 - 6 - 7 - 5. Then the nodes are inserted in the following order: 9 (between 6 and 7), 11 (between 7 and 9), 12 (between 7 and 11), 10 (between 9 and 11), 14 (between 10 and 11), 8 (between 9 and 10), 13 (between 8 and 10), 4 (between 8 and 9), 2 (between 4 and 9 ), 1 (between 2 and 4), 15 (between 11 and 12) and finally 3 (between 5 and 7). The resulting tour is

1 - 2 - 9 - 6 - 5 - 3 - 7 - 12 - 15 - 11 - 14 - 10 - 13 - 8 - 4 - 1

and has length 79. There is no improvement with 2-opt.

(c) We start Furthest Insertion with the tour 1 - 15 - 1 of length 46. Then city 3 is inserted followed by city 13. The new tour is 1 - 3 - 15 - 13 with length 60. The remaining nodes are inserted in the folowing order: 6 (between 13 and 15), 14 (between 6 and 13), 5 (between 6 and 15), 11 (between 5 and 15), 7 (between 5 and 11), 10 (between 13 and 14), 9 (between 6 and 14), 12 (between 11 and 15), 12 (between 11 and 15), 4 (between 1 and 13), 8 (between 4 and 13) and finally 2 (between 1 and 3). The resulting tour

1 - 2 - 3 - 15 - 12 - 11 - 7 - 5 - 6 - 9 - 14 - 10 - 13 - 8 - 4 - 1

has length 81. There is no improvement with 2-opt.

(d) We take as the central point on the map the midpoint between 5 and 10. The resulting tour obtained by applying the sweep heuristic is

7 - 3 - 5 - 6 - 2 - 1 - 4 - 8 - 9 - 13 - 10 - 14 - 11 - 15 - 12 - 7

and it has length 80.

Applying the 2-opt heuristic, we replace 9-13 and 10-14 by 9-10 and 13-14, thus reducing the length of the tour by 1. The new tour

1 - 2 - 6 - 5 - 3 - 7 - 12 - 15 - 11 - 14 - 13 - 10 - 9 - 8 - 4 - 1

has length 79.