Skip to content

Exercises · Local search

Exercises · Chapter 31 · each solution opens with a click · Chapter 31: Local search · Exercises, volume 4 (PDF)

Knapsack

Exercise 31.1: Local search KP 1

We consider a knapsack of capacity \(c = 18\) and a set \(\mathscr{I} = \{1,2,3,4,5\}\) of \(5\) items (\(n=5\)), with the following profits and weights:

\[ \begin{array}{l|ccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\[1ex] \hline {p_j} & {10} & {7} & {13} & {14} & {8} \\[1ex] {w_j} & {2} & {3} & {8} & {9} & {7} \\ \hline \end{array} \]

The items are sorted by non-increasing efficiency. The neighbourhood flip+swap contains the feasible vectors obtained by a flip (add or remove one item) or by a swap (remove a selected item \(j\), add an unselected item \(k\)); the flips are examined first, for \(j=1,\dots,n\), then the swaps, for increasing \(j\) and, for each \(j\), increasing \(k\). Ties in best improvement are broken in favour of the move examined first.

Questions

  1. Compute the solution of the greedy algorithm \(GR\) (by efficiency) and its profit.

  2. Apply the local search with the neighbourhood flip+swap and the best-improvement rule, starting from the solution of \(GR\). At every iteration list the neighbours, with their weight and profit, and state the move accepted.

  3. Compute the solution of the greedy by profit \(GR_p\), and apply the same local search starting from it.

  4. The optimal value is \(z(I)=32\). Which of the two local searches finds an optimal solution? Explain why the other one stops, by looking at the moves needed to reach the optimal solution.

Solution

  1. The efficiencies are \(\frac{10}{2}\), \(\frac{7}{3}\), \(\frac{13}{8}\), \(\frac{14}{9}\), \(\frac{8}{7}\), non-increasing. With \(rc=18\):

    • item \(1\) (\(w_{1}=2\)) is selected, \(rc=16\);

    • item \(2\) (\(w_{2}=3\)) is selected, \(rc=13\);

    • item \(3\) (\(w_{3}=8\)) is selected, \(rc=5\);

    • item \(4\) (\(w_{4}=9>rc=5\)) is not selected;

    • item \(5\) (\(w_{5}=7>rc=5\)) is not selected;

    \(GR\) returns \(x=(1,1,1,0,0)\), the items \(\{1,2,3\}\), of weight \(13\) and profit \(GR(I)=30\).

  2. Iteration 1: current solution \(x=(1,1,1,0,0)\), weight \(13\), profit \(30\).

    move neighbour weight profit
    flip \(1\) \((0,1,1,0,0)\) \(11\) \(20\)
    flip \(2\) \((1,0,1,0,0)\) \(10\) \(23\)
    flip \(3\) \((1,1,0,0,0)\) \(5\) \(17\)
    flip \(4\) \((1,1,1,1,0)\) \(22\) — infeasible
    flip \(5\) \((1,1,1,0,1)\) \(20\) — infeasible
    \(1\) out, \(4\) in \((0,1,1,1,0)\) \(20\) — infeasible
    \(1\) out, \(5\) in \((0,1,1,0,1)\) \(18\) \(28\)
    \(2\) out, \(4\) in \((1,0,1,1,0)\) \(19\) — infeasible
    \(2\) out, \(5\) in \((1,0,1,0,1)\) \(17\) \(31\) \(\leftarrow\) accepted
    \(3\) out, \(4\) in \((1,1,0,1,0)\) \(14\) \(31\)
    \(3\) out, \(5\) in \((1,1,0,0,1)\) \(12\) \(25\)

    The move is accepted after examining 7 feasible neighbours.

    Iteration 2: current solution \(x=(1,0,1,0,1)\), weight \(17\), profit \(31\).

    move neighbour weight profit
    flip \(1\) \((0,0,1,0,1)\) \(15\) \(21\)
    flip \(2\) \((1,1,1,0,1)\) \(20\) — infeasible
    flip \(3\) \((1,0,0,0,1)\) \(9\) \(18\)
    flip \(4\) \((1,0,1,1,1)\) \(26\) — infeasible
    flip \(5\) \((1,0,1,0,0)\) \(10\) \(23\)
    \(1\) out, \(2\) in \((0,1,1,0,1)\) \(18\) \(28\)
    \(1\) out, \(4\) in \((0,0,1,1,1)\) \(24\) — infeasible
    \(3\) out, \(2\) in \((1,1,0,0,1)\) \(12\) \(25\)
    \(3\) out, \(4\) in \((1,0,0,1,1)\) \(18\) \(32\) \(\leftarrow\) accepted
    \(5\) out, \(2\) in \((1,1,1,0,0)\) \(13\) \(30\)
    \(5\) out, \(4\) in \((1,0,1,1,0)\) \(19\) — infeasible

    The move is accepted after examining 7 feasible neighbours.

    Iteration 3: current solution \(x=(1,0,0,1,1)\), weight \(18\), profit \(32\).

    move neighbour weight profit
    flip \(1\) \((0,0,0,1,1)\) \(16\) \(22\)
    flip \(2\) \((1,1,0,1,1)\) \(21\) — infeasible
    flip \(3\) \((1,0,1,1,1)\) \(26\) — infeasible
    flip \(4\) \((1,0,0,0,1)\) \(9\) \(18\)
    flip \(5\) \((1,0,0,1,0)\) \(11\) \(24\)
    \(1\) out, \(2\) in \((0,1,0,1,1)\) \(19\) — infeasible
    \(1\) out, \(3\) in \((0,0,1,1,1)\) \(24\) — infeasible
    \(4\) out, \(2\) in \((1,1,0,0,1)\) \(12\) \(25\)
    \(4\) out, \(3\) in \((1,0,1,0,1)\) \(17\) \(31\)
    \(5\) out, \(2\) in \((1,1,0,1,0)\) \(14\) \(31\)
    \(5\) out, \(3\) in \((1,0,1,1,0)\) \(19\) — infeasible

    No feasible neighbour has a larger profit: \(x=(1,0,0,1,1)\) is a local optimum, of profit \(32\) (6 feasible neighbours examined).

    The local search makes 2 moves, \(30\to31\to32\), and stops in \(x=(1,0,0,1,1)\), of profit \(32\).

  3. The items by non-increasing profit are \((4,3,1,5,2)\). With \(rc=18\):

    • item \(4\) (\(w_{4}=9\)) is selected, \(rc=9\);

    • item \(3\) (\(w_{3}=8\)) is selected, \(rc=1\);

    • item \(1\) (\(w_{1}=2>rc=1\)) is not selected;

    • item \(5\) (\(w_{5}=7>rc=1\)) is not selected;

    • item \(2\) (\(w_{2}=3>rc=1\)) is not selected;

    The greedy algorithm by profit returns \(x=(0,0,1,1,0)\), of weight \(17\) and profit \(27\).

    Iteration 1: current solution \(x=(0,0,1,1,0)\), weight \(17\), profit \(27\).

    move neighbour weight profit
    flip \(1\) \((1,0,1,1,0)\) \(19\) — infeasible
    flip \(2\) \((0,1,1,1,0)\) \(20\) — infeasible
    flip \(3\) \((0,0,0,1,0)\) \(9\) \(14\)
    flip \(4\) \((0,0,1,0,0)\) \(8\) \(13\)
    flip \(5\) \((0,0,1,1,1)\) \(24\) — infeasible
    \(3\) out, \(1\) in \((1,0,0,1,0)\) \(11\) \(24\)
    \(3\) out, \(2\) in \((0,1,0,1,0)\) \(12\) \(21\)
    \(3\) out, \(5\) in \((0,0,0,1,1)\) \(16\) \(22\)
    \(4\) out, \(1\) in \((1,0,1,0,0)\) \(10\) \(23\)
    \(4\) out, \(2\) in \((0,1,1,0,0)\) \(11\) \(20\)
    \(4\) out, \(5\) in \((0,0,1,0,1)\) \(15\) \(21\)

    No feasible neighbour has a larger profit: \(x=(0,0,1,1,0)\) is a local optimum, of profit \(27\) (8 feasible neighbours examined).

  4. The local search from \(GR\) reaches \(x=(1,0,0,1,1)\), of profit \(32=z(I)\): an optimal solution. The local search from the greedy solution by profit stops immediately in \(x=(0,0,1,1,0)\), of profit \(27\), a local optimum that is not optimal. To go from \(\{3,4\}\) to the optimal set \(\{1,4,5\}\) one must remove item \(3\) and add the items \(1\) and \(5\): three flips, or one swap and one flip, and every intermediate vector is either infeasible or worse. The local optimum reached depends on the starting solution.

Exercise 31.2: Local search KP 2

We consider a knapsack of capacity \(c = 13\) and a set \(\mathscr{I} = \{1,2,3,4,5\}\) of \(5\) items (\(n=5\)), with the following profits and weights:

\[ \begin{array}{l|ccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\[1ex] \hline {p_j} & {8} & {9} & {14} & {11} & {9} \\[1ex] {w_j} & {3} & {5} & {9} & {9} & {8} \\ \hline \end{array} \]

The items are sorted by non-increasing efficiency. The neighbourhood flip+swap contains the feasible vectors obtained by a flip (add or remove one item) or by a swap (remove a selected item \(j\), add an unselected item \(k\)); the flips are examined first, for \(j=1,\dots,n\), then the swaps, for increasing \(j\) and, for each \(j\), increasing \(k\). Ties in best improvement are broken in favour of the move examined first.

Questions

  1. Compute the solution of the greedy algorithm \(GR\) (by efficiency) and its profit.

  2. Apply the local search with the neighbourhood flip+swap and the first-improvement rule, starting from the solution of \(GR\).

  3. Apply the same local search with the best-improvement rule, starting from the solution of \(GR\).

  4. Compare the two local optima, and the number of feasible neighbours examined by the two rules. Is one of the two local optima optimal? (Hint: the LP relaxation bound is not enough here; split the solutions according to whether item \(3\) is selected.)

Solution

  1. The efficiencies are \(\frac{8}{3}\), \(\frac{9}{5}\), \(\frac{14}{9}\), \(\frac{11}{9}\), \(\frac{9}{8}\), non-increasing. With \(rc=13\):

    • item \(1\) (\(w_{1}=3\)) is selected, \(rc=10\);

    • item \(2\) (\(w_{2}=5\)) is selected, \(rc=5\);

    • item \(3\) (\(w_{3}=9>rc=5\)) is not selected;

    • item \(4\) (\(w_{4}=9>rc=5\)) is not selected;

    • item \(5\) (\(w_{5}=8>rc=5\)) is not selected;

    \(GR\) returns \(x=(1,1,0,0,0)\), of weight \(8\) and profit \(GR(I)=17\).

  2. Iteration 1: current solution \(x=(1,1,0,0,0)\), weight \(8\), profit \(17\).

    move neighbour weight profit
    flip \(1\) \((0,1,0,0,0)\) \(5\) \(9\)
    flip \(2\) \((1,0,0,0,0)\) \(3\) \(8\)
    flip \(3\) \((1,1,1,0,0)\) \(17\) — infeasible
    flip \(4\) \((1,1,0,1,0)\) \(17\) — infeasible
    flip \(5\) \((1,1,0,0,1)\) \(16\) — infeasible
    \(1\) out, \(3\) in \((0,1,1,0,0)\) \(14\) — infeasible
    \(1\) out, \(4\) in \((0,1,0,1,0)\) \(14\) — infeasible
    \(1\) out, \(5\) in \((0,1,0,0,1)\) \(13\) \(18\) \(\leftarrow\) accepted
    \(2\) out, \(3\) in \((1,0,1,0,0)\) \(12\) \(22\)
    \(2\) out, \(4\) in \((1,0,0,1,0)\) \(12\) \(19\)
    \(2\) out, \(5\) in \((1,0,0,0,1)\) \(11\) \(17\)

    The move is accepted after examining 3 feasible neighbours.

    Iteration 2: current solution \(x=(0,1,0,0,1)\), weight \(13\), profit \(18\).

    move neighbour weight profit
    flip \(1\) \((1,1,0,0,1)\) \(16\) — infeasible
    flip \(2\) \((0,0,0,0,1)\) \(8\) \(9\)
    flip \(3\) \((0,1,1,0,1)\) \(22\) — infeasible
    flip \(4\) \((0,1,0,1,1)\) \(22\) — infeasible
    flip \(5\) \((0,1,0,0,0)\) \(5\) \(9\)
    \(2\) out, \(1\) in \((1,0,0,0,1)\) \(11\) \(17\)
    \(2\) out, \(3\) in \((0,0,1,0,1)\) \(17\) — infeasible
    \(2\) out, \(4\) in \((0,0,0,1,1)\) \(17\) — infeasible
    \(5\) out, \(1\) in \((1,1,0,0,0)\) \(8\) \(17\)
    \(5\) out, \(3\) in \((0,1,1,0,0)\) \(14\) — infeasible
    \(5\) out, \(4\) in \((0,1,0,1,0)\) \(14\) — infeasible

    No feasible neighbour has a larger profit: \(x=(0,1,0,0,1)\) is a local optimum, of profit \(18\) (4 feasible neighbours examined).

    First improvement stops in \(x=(0,1,0,0,1)\), of profit \(18\), after examining 7 feasible neighbours in total.

  3. Iteration 1: current solution \(x=(1,1,0,0,0)\), weight \(8\), profit \(17\).

    move neighbour weight profit
    flip \(1\) \((0,1,0,0,0)\) \(5\) \(9\)
    flip \(2\) \((1,0,0,0,0)\) \(3\) \(8\)
    flip \(3\) \((1,1,1,0,0)\) \(17\) — infeasible
    flip \(4\) \((1,1,0,1,0)\) \(17\) — infeasible
    flip \(5\) \((1,1,0,0,1)\) \(16\) — infeasible
    \(1\) out, \(3\) in \((0,1,1,0,0)\) \(14\) — infeasible
    \(1\) out, \(4\) in \((0,1,0,1,0)\) \(14\) — infeasible
    \(1\) out, \(5\) in \((0,1,0,0,1)\) \(13\) \(18\)
    \(2\) out, \(3\) in \((1,0,1,0,0)\) \(12\) \(22\) \(\leftarrow\) accepted
    \(2\) out, \(4\) in \((1,0,0,1,0)\) \(12\) \(19\)
    \(2\) out, \(5\) in \((1,0,0,0,1)\) \(11\) \(17\)

    The move is accepted after examining 6 feasible neighbours.

    Iteration 2: current solution \(x=(1,0,1,0,0)\), weight \(12\), profit \(22\).

    move neighbour weight profit
    flip \(1\) \((0,0,1,0,0)\) \(9\) \(14\)
    flip \(2\) \((1,1,1,0,0)\) \(17\) — infeasible
    flip \(3\) \((1,0,0,0,0)\) \(3\) \(8\)
    flip \(4\) \((1,0,1,1,0)\) \(21\) — infeasible
    flip \(5\) \((1,0,1,0,1)\) \(20\) — infeasible
    \(1\) out, \(2\) in \((0,1,1,0,0)\) \(14\) — infeasible
    \(1\) out, \(4\) in \((0,0,1,1,0)\) \(18\) — infeasible
    \(1\) out, \(5\) in \((0,0,1,0,1)\) \(17\) — infeasible
    \(3\) out, \(2\) in \((1,1,0,0,0)\) \(8\) \(17\)
    \(3\) out, \(4\) in \((1,0,0,1,0)\) \(12\) \(19\)
    \(3\) out, \(5\) in \((1,0,0,0,1)\) \(11\) \(17\)

    No feasible neighbour has a larger profit: \(x=(1,0,1,0,0)\) is a local optimum, of profit \(22\) (5 feasible neighbours examined).

    Best improvement stops in \(x=(1,0,1,0,0)\), of profit \(22\), after examining 11 feasible neighbours in total.

  4. First improvement accepts the first improving swap it finds, which gains only \(1\), and stops in a local optimum of profit \(18\); best improvement takes the largest gain and reaches profit \(22\). They examine 7 and 11 feasible neighbours. The LP relaxation gives \(z(I)\le 8+9+14\cdot\frac{5}{9}=\frac{223}{9}\), hence \(z(I)\le 24\), which does not prove that \(22\) is optimal. We argue directly. If item \(3\) is selected, the residual capacity is \(4\) and only item \(1\) fits, for a profit of \(22\). If item \(3\) is not selected, the best solution is \(\{1,4\}\), of profit \(19\). Hence \(z(I)=22\) and the solution of best improvement, \(x=(1,0,1,0,0)\), is optimal. From the same starting solution the two rules reach different local optima.

Exercise 31.3: Local search KP 3

We consider a knapsack of capacity \(c = 11\) and a set \(\mathscr{I} = \{1,2,3,4,5\}\) of \(5\) items (\(n=5\)), with the following profits and weights:

\[ \begin{array}{l|ccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\[1ex] \hline {p_j} & {14} & {7} & {10} & {8} & {6} \\[1ex] {w_j} & {4} & {4} & {7} & {7} & {9} \\ \hline \end{array} \]

The items are sorted by non-increasing efficiency. With penalties, the local search maximizes \(g_\alpha(x)=\sum_j p_jx_j-\alpha\max\{0,\sum_j w_jx_j-c\}\) over all the binary vectors, with the flip neighbourhood (flips examined for \(j=1,\dots,n\)) and the best-improvement rule.

Questions

  1. Compute the solution of \(GR\), and show that it is a local optimum for the flip neighbourhood restricted to feasible vectors.

  2. Apply the penalty flip local search with \(\alpha=1\), starting from the solution of \(GR\). Is the local optimum feasible? Which solution should the search return?

  3. Apply the penalty flip local search with \(\alpha=2\), starting from the solution of \(GR\).

  4. Apply it with \(\alpha=3\). The optimal value is \(z(I)=24\): discuss the role of \(\alpha\), and state for which values of \(\alpha\) the local optima are surely feasible.

Solution

  1. With \(rc=11\):

    • item \(1\) (\(w_{1}=4\)) is selected, \(rc=7\);

    • item \(2\) (\(w_{2}=4\)) is selected, \(rc=3\);

    • item \(3\) (\(w_{3}=7>rc=3\)) is not selected;

    • item \(4\) (\(w_{4}=7>rc=3\)) is not selected;

    • item \(5\) (\(w_{5}=9>rc=3\)) is not selected;

    \(GR\) returns \(x=(1,1,0,0,0)\), of weight \(8\) and profit \(21\). Its flips are

    move neighbour weight profit
    flip \(1\) \((0,1,0,0,0)\) \(4\) \(7\)
    flip \(2\) \((1,0,0,0,0)\) \(4\) \(14\)
    flip \(3\) \((1,1,1,0,0)\) \(15\) — infeasible
    flip \(4\) \((1,1,0,1,0)\) \(15\) — infeasible
    flip \(5\) \((1,1,0,0,1)\) \(17\) — infeasible

    The feasible neighbours remove an item and have a smaller profit: \(x\) is a local optimum for the feasible flip neighbourhood.

  2. Iteration 1: \(x=(1,1,0,0,0)\), weight \(8\), \(g_{1}(x)=21\).

    move neighbour weight excess \(g_{1}\)
    flip \(1\) \((0,1,0,0,0)\) \(4\) \(0\) \(7-1\cdot0=7\)
    flip \(2\) \((1,0,0,0,0)\) \(4\) \(0\) \(14-1\cdot0=14\)
    flip \(3\) \((1,1,1,0,0)\) \(15\) \(4\) \(31-1\cdot4=27\) \(\leftarrow\)
    flip \(4\) \((1,1,0,1,0)\) \(15\) \(4\) \(29-1\cdot4=25\)
    flip \(5\) \((1,1,0,0,1)\) \(17\) \(6\) \(27-1\cdot6=21\)

    Iteration 2: \(x=(1,1,1,0,0)\), weight \(15\), \(g_{1}(x)=27\).

    move neighbour weight excess \(g_{1}\)
    flip \(1\) \((0,1,1,0,0)\) \(11\) \(0\) \(17-1\cdot0=17\)
    flip \(2\) \((1,0,1,0,0)\) \(11\) \(0\) \(24-1\cdot0=24\)
    flip \(3\) \((1,1,0,0,0)\) \(8\) \(0\) \(21-1\cdot0=21\)
    flip \(4\) \((1,1,1,1,0)\) \(22\) \(11\) \(39-1\cdot11=28\) \(\leftarrow\)
    flip \(5\) \((1,1,1,0,1)\) \(24\) \(13\) \(37-1\cdot13=24\)

    Iteration 3: \(x=(1,1,1,1,0)\), weight \(22\), \(g_{1}(x)=28\).

    move neighbour weight excess \(g_{1}\)
    flip \(1\) \((0,1,1,1,0)\) \(18\) \(7\) \(25-1\cdot7=18\)
    flip \(2\) \((1,0,1,1,0)\) \(18\) \(7\) \(32-1\cdot7=25\)
    flip \(3\) \((1,1,0,1,0)\) \(15\) \(4\) \(29-1\cdot4=25\)
    flip \(4\) \((1,1,1,0,0)\) \(15\) \(4\) \(31-1\cdot4=27\)
    flip \(5\) \((1,1,1,1,1)\) \(31\) \(20\) \(45-1\cdot20=25\)

    No flip increases \(g_{1}\): the search stops in \(x=(1,1,1,1,0)\), of weight \(22\) and profit \(39\).

    The local optimum is infeasible (weight \(22>11\)): the penalty is too small. The search must return the best feasible vector visited, \((1,1,0,0,0)\), of profit \(21\), i.e., the starting solution.

  3. Iteration 1: \(x=(1,1,0,0,0)\), weight \(8\), \(g_{2}(x)=21\).

    move neighbour weight excess \(g_{2}\)
    flip \(1\) \((0,1,0,0,0)\) \(4\) \(0\) \(7-2\cdot0=7\)
    flip \(2\) \((1,0,0,0,0)\) \(4\) \(0\) \(14-2\cdot0=14\)
    flip \(3\) \((1,1,1,0,0)\) \(15\) \(4\) \(31-2\cdot4=23\) \(\leftarrow\)
    flip \(4\) \((1,1,0,1,0)\) \(15\) \(4\) \(29-2\cdot4=21\)
    flip \(5\) \((1,1,0,0,1)\) \(17\) \(6\) \(27-2\cdot6=15\)

    Iteration 2: \(x=(1,1,1,0,0)\), weight \(15\), \(g_{2}(x)=23\).

    move neighbour weight excess \(g_{2}\)
    flip \(1\) \((0,1,1,0,0)\) \(11\) \(0\) \(17-2\cdot0=17\)
    flip \(2\) \((1,0,1,0,0)\) \(11\) \(0\) \(24-2\cdot0=24\) \(\leftarrow\)
    flip \(3\) \((1,1,0,0,0)\) \(8\) \(0\) \(21-2\cdot0=21\)
    flip \(4\) \((1,1,1,1,0)\) \(22\) \(11\) \(39-2\cdot11=17\)
    flip \(5\) \((1,1,1,0,1)\) \(24\) \(13\) \(37-2\cdot13=11\)

    Iteration 3: \(x=(1,0,1,0,0)\), weight \(11\), \(g_{2}(x)=24\).

    move neighbour weight excess \(g_{2}\)
    flip \(1\) \((0,0,1,0,0)\) \(7\) \(0\) \(10-2\cdot0=10\)
    flip \(2\) \((1,1,1,0,0)\) \(15\) \(4\) \(31-2\cdot4=23\)
    flip \(3\) \((1,0,0,0,0)\) \(4\) \(0\) \(14-2\cdot0=14\)
    flip \(4\) \((1,0,1,1,0)\) \(18\) \(7\) \(32-2\cdot7=18\)
    flip \(5\) \((1,0,1,0,1)\) \(20\) \(9\) \(30-2\cdot9=12\)

    No flip increases \(g_{2}\): the search stops in \(x=(1,0,1,0,0)\), of weight \(11\) and profit \(24\).

    The local optimum \((1,0,1,0,0)\) is feasible, of profit \(24=z(I)\): it is optimal. The search reached it through the infeasible vector \((1,1,1,0,0)\).

  4. Iteration 1: \(x=(1,1,0,0,0)\), weight \(8\), \(g_{3}(x)=21\).

    move neighbour weight excess \(g_{3}\)
    flip \(1\) \((0,1,0,0,0)\) \(4\) \(0\) \(7-3\cdot0=7\)
    flip \(2\) \((1,0,0,0,0)\) \(4\) \(0\) \(14-3\cdot0=14\)
    flip \(3\) \((1,1,1,0,0)\) \(15\) \(4\) \(31-3\cdot4=19\)
    flip \(4\) \((1,1,0,1,0)\) \(15\) \(4\) \(29-3\cdot4=17\)
    flip \(5\) \((1,1,0,0,1)\) \(17\) \(6\) \(27-3\cdot6=9\)

    No flip increases \(g_{3}\): the search stops in \(x=(1,1,0,0,0)\), of weight \(8\) and profit \(21\).

    With \(\alpha=3\) the search does not move: it behaves as the feasible search and stops in the solution of \(GR\), of profit \(21\). A small \(\alpha\) (\(1\)) lets the search stop among infeasible vectors; a large \(\alpha\) (\(3\)) forbids it to cross the infeasible region; here only \(\alpha=2\) reaches the optimum. If \(\alpha>\max_j p_j=14\), every infeasible vector has an improving flip (removing any selected item decreases the excess by at least \(1\) and gains at least \(\alpha-p_j>0\)), so all the local optima are feasible; but then, from a feasible vector, no flip that creates an excess is improving, and the search never leaves the feasible region.

Bin packing

Exercise 31.4: Local search BPP 1

Bins of capacity \(c=10\) and a set \(\mathscr{I}=\{1,2,3,4,5,6,7\}\) of \(7\) items with weights

\[ \begin{array}{l|ccccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} & {j=7} \\[1ex] \hline {w_j} & {2} & {3} & {2} & {7} & {4} & {7} & {4} \\ \hline \end{array} \]

The bins are labelled \(1,2,\dots\) in the order in which \(FF\) opens them, and keep their label. A move puts one item into another non-empty bin where it fits (examined for \(j=1,\dots,n\) and, for each \(j\), for increasing bin label); a swap exchanges two items \(j<k\) of different weight in different bins, if both bins stay feasible. The auxiliary objective \(SQ=\sum_b L_b^2\) is maximized; the gain of a transfer of \(\delta\) from bin \(a\) to bin \(b\) is \(2\delta(L_b-L_a+\delta)\) (a move of item \(j\) transfers \(\delta=w_j\), a swap of item \(j\) in bin \(a\) and item \(k\) in bin \(b\) transfers \(\delta=w_j-w_k\)). Best improvement breaks ties in favour of the move examined first.

Questions

  1. Compute the solution of First Fit (\(FF\)), its number of bins and the lower bound \(\lceil\sum_j w_j/c\rceil\).

  2. Apply the move local search with the objective \(nb\) (number of bins), starting from the solution of \(FF\). Why does it stop?

  3. Apply the move local search with the auxiliary objective \(SQ=\sum_b L_b^2\) and the best-improvement rule, starting from the solution of \(FF\).

  4. Is the final solution optimal? Explain the different behaviour of the two objectives.

Solution

    • item \(1\) (\(w_{1}=2\)) goes into bin \(1\), opened for it, load \(2\);

    • item \(2\) (\(w_{2}=3\)) goes into bin \(1\), load \(5\);

    • item \(3\) (\(w_{3}=2\)) goes into bin \(1\), load \(7\);

    • item \(4\) (\(w_{4}=7\)) fits in no open bin: bin \(2\) is opened, load \(7\);

    • item \(5\) (\(w_{5}=4\)) fits in no open bin: bin \(3\) is opened, load \(4\);

    • item \(6\) (\(w_{6}=7\)) fits in no open bin: bin \(4\) is opened, load \(7\);

    • item \(7\) (\(w_{7}=4\)) goes into bin \(3\), load \(8\);

    \(FF\) uses \(nb=4\) bins, with packing patterns \(\{1,2,3\}, \{4\}, \{5,7\}, \{6\}\) and loads \((7,7,8,7)\). The lower bound is \(\lceil 29/10\rceil=3\).

  2. Iteration 1 (move): packing patterns \(\{1,2,3\}, \{4\}, \{5,7\}, \{6\}\), loads \((7,7,8,7)\), \(nb=4\), \(SQ=211\).

    move loads bin emptied
    item \(1\): bin \(1\to 2\) \((5,9,8,7)\) no
    item \(1\): bin \(1\to 3\) \((5,7,10,7)\) no
    item \(1\): bin \(1\to 4\) \((5,7,8,9)\) no
    item \(2\): bin \(1\to 2\) \((4,10,8,7)\) no
    item \(2\): bin \(1\to 4\) \((4,7,8,10)\) no
    item \(3\): bin \(1\to 2\) \((5,9,8,7)\) no
    item \(3\): bin \(1\to 3\) \((5,7,10,7)\) no
    item \(3\): bin \(1\to 4\) \((5,7,8,9)\) no

    No move is improving.

    No move empties a bin, so no move decreases \(nb\): the solution of \(FF\) is a local optimum with \(4\) bins. All the moves are neutral for \(nb\): the search is on a plateau.

  3. Iteration 1 (move): packing patterns \(\{1,2,3\}, \{4\}, \{5,7\}, \{6\}\), loads \((7,7,8,7)\), \(nb=4\), \(SQ=211\).

    move loads gain
    item \(1\): bin \(1\to 2\) \((5,9,8,7)\) \(2\cdot2\cdot(7-7+2)=8\)
    item \(1\): bin \(1\to 3\) \((5,7,10,7)\) \(2\cdot2\cdot(8-7+2)=12\)
    item \(1\): bin \(1\to 4\) \((5,7,8,9)\) \(2\cdot2\cdot(7-7+2)=8\)
    item \(2\): bin \(1\to 2\) \((4,10,8,7)\) \(2\cdot3\cdot(7-7+3)=18\) \(\leftarrow\)
    item \(2\): bin \(1\to 4\) \((4,7,8,10)\) \(2\cdot3\cdot(7-7+3)=18\)
    item \(3\): bin \(1\to 2\) \((5,9,8,7)\) \(2\cdot2\cdot(7-7+2)=8\)
    item \(3\): bin \(1\to 3\) \((5,7,10,7)\) \(2\cdot2\cdot(8-7+2)=12\)
    item \(3\): bin \(1\to 4\) \((5,7,8,9)\) \(2\cdot2\cdot(7-7+2)=8\)

    The move marked is accepted.

    Iteration 2 (move): packing patterns \(\{1,3\}, \{2,4\}, \{5,7\}, \{6\}\), loads \((4,10,8,7)\), \(nb=4\), \(SQ=229\).

    move loads gain
    item \(1\): bin \(1\to 3\) \((2,10,10,7)\) \(2\cdot2\cdot(8-4+2)=24\) \(\leftarrow\)
    item \(1\): bin \(1\to 4\) \((2,10,8,9)\) \(2\cdot2\cdot(7-4+2)=20\)
    item \(2\): bin \(2\to 1\) \((7,7,8,7)\) \(2\cdot3\cdot(4-10+3)=-18\)
    item \(2\): bin \(2\to 4\) \((4,7,8,10)\) \(2\cdot3\cdot(7-10+3)=0\)
    item \(3\): bin \(1\to 3\) \((2,10,10,7)\) \(2\cdot2\cdot(8-4+2)=24\)
    item \(3\): bin \(1\to 4\) \((2,10,8,9)\) \(2\cdot2\cdot(7-4+2)=20\)
    item \(5\): bin \(3\to 1\) \((8,10,4,7)\) \(2\cdot4\cdot(4-8+4)=0\)
    item \(7\): bin \(3\to 1\) \((8,10,4,7)\) \(2\cdot4\cdot(4-8+4)=0\)

    The move marked is accepted.

    Iteration 3 (move): packing patterns \(\{3\}, \{2,4\}, \{1,5,7\}, \{6\}\), loads \((2,10,10,7)\), \(nb=4\), \(SQ=253\).

    move loads gain
    item \(1\): bin \(3\to 1\) \((4,10,8,7)\) \(2\cdot2\cdot(2-10+2)=-24\)
    item \(1\): bin \(3\to 4\) \((2,10,8,9)\) \(2\cdot2\cdot(7-10+2)=-4\)
    item \(2\): bin \(2\to 1\) \((5,7,10,7)\) \(2\cdot3\cdot(2-10+3)=-30\)
    item \(2\): bin \(2\to 4\) \((2,7,10,10)\) \(2\cdot3\cdot(7-10+3)=0\)
    item \(3\): bin \(1\to 4\) \((10,10,9)\) \(2\cdot2\cdot(7-2+2)=28\) \(\leftarrow\)
    item \(4\): bin \(2\to 1\) \((9,3,10,7)\) \(2\cdot7\cdot(2-10+7)=-14\)
    item \(5\): bin \(3\to 1\) \((6,10,6,7)\) \(2\cdot4\cdot(2-10+4)=-32\)
    item \(6\): bin \(4\to 1\) \((9,10,10)\) \(2\cdot7\cdot(2-7+7)=28\)
    item \(7\): bin \(3\to 1\) \((6,10,6,7)\) \(2\cdot4\cdot(2-10+4)=-32\)

    The move marked is accepted.

    Iteration 4 (move): packing patterns \(\{2,4\}, \{1,5,7\}, \{3,6\}\), loads \((10,10,9)\), \(nb=3\), \(SQ=281\). There is no feasible move.

    The search makes 3 moves, with \(SQ\): \(211\to229\to253\to281\), and stops with packing patterns \(\{2,4\}, \{1,5,7\}, \{3,6\}\) and \(nb=3\).

  4. The final solution uses \(3=\lceil 29/10\rceil\) bins: it is optimal. With \(nb\) the search sees no difference between the neighbours, since only a move that empties a bin changes \(nb\); with \(SQ\) the moves that make a heavy bin heavier and a light bin lighter are improving, and they prepare the move that empties a bin (which always increases \(SQ\)).

Exercise 31.5: Local search BPP 2

Bins of capacity \(c=10\) and a set \(\mathscr{I}=\{1,2,3,4,5,6\}\) of \(6\) items with weights

\[ \begin{array}{l|cccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\[1ex] \hline {w_j} & {2} & {3} & {4} & {5} & {4} & {2} \\ \hline \end{array} \]

The bins are labelled \(1,2,\dots\) in the order in which \(FF\) opens them, and keep their label. A move puts one item into another non-empty bin where it fits (examined for \(j=1,\dots,n\) and, for each \(j\), for increasing bin label); a swap exchanges two items \(j<k\) of different weight in different bins, if both bins stay feasible. The auxiliary objective \(SQ=\sum_b L_b^2\) is maximized; the gain of a transfer of \(\delta\) from bin \(a\) to bin \(b\) is \(2\delta(L_b-L_a+\delta)\) (a move of item \(j\) transfers \(\delta=w_j\), a swap of item \(j\) in bin \(a\) and item \(k\) in bin \(b\) transfers \(\delta=w_j-w_k\)). Best improvement breaks ties in favour of the move examined first.

Questions

  1. Compute the solution of First Fit (\(FF\)) and the lower bound \(\lceil\sum_j w_j/c\rceil\).

  2. Apply the move local search with the auxiliary objective \(SQ\) and the best-improvement rule, starting from the solution of \(FF\).

  3. Apply the swap local search with the objective \(SQ\) and the best-improvement rule, starting from the solution of \(FF\).

  4. Apply the variable neighbourhood descent with \(N_1=\) move and \(N_2=\) swap (objective \(SQ\), best improvement), starting from the solution of \(FF\). Is the result optimal? What do the three local searches show?

Solution

    • item \(1\) (\(w_{1}=2\)) goes into bin \(1\), opened for it, load \(2\);

    • item \(2\) (\(w_{2}=3\)) goes into bin \(1\), load \(5\);

    • item \(3\) (\(w_{3}=4\)) goes into bin \(1\), load \(9\);

    • item \(4\) (\(w_{4}=5\)) fits in no open bin: bin \(2\) is opened, load \(5\);

    • item \(5\) (\(w_{5}=4\)) goes into bin \(2\), load \(9\);

    • item \(6\) (\(w_{6}=2\)) fits in no open bin: bin \(3\) is opened, load \(2\);

    \(FF\) uses \(nb=3\) bins, with packing patterns \(\{1,2,3\}, \{4,5\}, \{6\}\) and loads \((9,9,2)\). The lower bound is \(\lceil 20/10\rceil=2\).

  2. Iteration 1 (move): packing patterns \(\{1,2,3\}, \{4,5\}, \{6\}\), loads \((9,9,2)\), \(nb=3\), \(SQ=166\).

    move loads gain
    item \(1\): bin \(1\to 3\) \((7,9,4)\) \(2\cdot2\cdot(2-9+2)=-20\)
    item \(2\): bin \(1\to 3\) \((6,9,5)\) \(2\cdot3\cdot(2-9+3)=-24\)
    item \(3\): bin \(1\to 3\) \((5,9,6)\) \(2\cdot4\cdot(2-9+4)=-24\)
    item \(4\): bin \(2\to 3\) \((9,4,7)\) \(2\cdot5\cdot(2-9+5)=-20\)
    item \(5\): bin \(2\to 3\) \((9,5,6)\) \(2\cdot4\cdot(2-9+4)=-24\)

    No move is improving.

    The solution of \(FF\) is a local optimum for move, with \(3\) bins.

  3. Iteration 1 (swap): packing patterns \(\{1,2,3\}, \{4,5\}, \{6\}\), loads \((9,9,2)\), \(nb=3\), \(SQ=166\).

    swap loads gain
    items \(2,5\) (bins \(1,2\)) \((10,8,2)\) \(2\cdot(-1)\cdot(9-9-1)=2\) \(\leftarrow\)
    items \(2,6\) (bins \(1,3\)) \((8,9,3)\) \(2\cdot(1)\cdot(2-9+1)=-12\)
    items \(3,4\) (bins \(1,2\)) \((10,8,2)\) \(2\cdot(-1)\cdot(9-9-1)=2\)
    items \(3,6\) (bins \(1,3\)) \((7,9,4)\) \(2\cdot(2)\cdot(2-9+2)=-20\)
    items \(4,6\) (bins \(2,3\)) \((9,6,5)\) \(2\cdot(3)\cdot(2-9+3)=-24\)
    items \(5,6\) (bins \(2,3\)) \((9,7,4)\) \(2\cdot(2)\cdot(2-9+2)=-20\)

    The swap marked is accepted.

    Iteration 2 (swap): packing patterns \(\{1,3,5\}, \{2,4\}, \{6\}\), loads \((10,8,2)\), \(nb=3\), \(SQ=168\).

    swap loads gain
    items \(2,3\) (bins \(2,1\)) \((9,9,2)\) \(2\cdot(-1)\cdot(10-8-1)=-2\)
    items \(2,5\) (bins \(2,1\)) \((9,9,2)\) \(2\cdot(-1)\cdot(10-8-1)=-2\)
    items \(2,6\) (bins \(2,3\)) \((10,7,3)\) \(2\cdot(1)\cdot(2-8+1)=-10\)
    items \(3,6\) (bins \(1,3\)) \((8,8,4)\) \(2\cdot(2)\cdot(2-10+2)=-24\)
    items \(4,6\) (bins \(2,3\)) \((10,5,5)\) \(2\cdot(3)\cdot(2-8+3)=-18\)
    items \(5,6\) (bins \(1,3\)) \((8,8,4)\) \(2\cdot(2)\cdot(2-10+2)=-24\)

    No swap is improving.

    The swap local search stops with packing patterns \(\{1,3,5\}, \{2,4\}, \{6\}\), \(SQ=168\), still \(3\) bins (a swap never changes \(nb\)).

  4. Iteration 1 (move): packing patterns \(\{1,2,3\}, \{4,5\}, \{6\}\), loads \((9,9,2)\), \(nb=3\), \(SQ=166\).

    move loads gain
    item \(1\): bin \(1\to 3\) \((7,9,4)\) \(2\cdot2\cdot(2-9+2)=-20\)
    item \(2\): bin \(1\to 3\) \((6,9,5)\) \(2\cdot3\cdot(2-9+3)=-24\)
    item \(3\): bin \(1\to 3\) \((5,9,6)\) \(2\cdot4\cdot(2-9+4)=-24\)
    item \(4\): bin \(2\to 3\) \((9,4,7)\) \(2\cdot5\cdot(2-9+5)=-20\)
    item \(5\): bin \(2\to 3\) \((9,5,6)\) \(2\cdot4\cdot(2-9+4)=-24\)

    No move is improving.

    Iteration 2 (swap): packing patterns \(\{1,2,3\}, \{4,5\}, \{6\}\), loads \((9,9,2)\), \(nb=3\), \(SQ=166\).

    swap loads gain
    items \(2,5\) (bins \(1,2\)) \((10,8,2)\) \(2\cdot(-1)\cdot(9-9-1)=2\) \(\leftarrow\)
    items \(2,6\) (bins \(1,3\)) \((8,9,3)\) \(2\cdot(1)\cdot(2-9+1)=-12\)
    items \(3,4\) (bins \(1,2\)) \((10,8,2)\) \(2\cdot(-1)\cdot(9-9-1)=2\)
    items \(3,6\) (bins \(1,3\)) \((7,9,4)\) \(2\cdot(2)\cdot(2-9+2)=-20\)
    items \(4,6\) (bins \(2,3\)) \((9,6,5)\) \(2\cdot(3)\cdot(2-9+3)=-24\)
    items \(5,6\) (bins \(2,3\)) \((9,7,4)\) \(2\cdot(2)\cdot(2-9+2)=-20\)

    The swap marked is accepted, and the search goes back to the move neighbourhood.

    Iteration 3 (move): packing patterns \(\{1,3,5\}, \{2,4\}, \{6\}\), loads \((10,8,2)\), \(nb=3\), \(SQ=168\).

    move loads gain
    item \(1\): bin \(1\to 2\) \((8,10,2)\) \(2\cdot2\cdot(8-10+2)=0\)
    item \(1\): bin \(1\to 3\) \((8,8,4)\) \(2\cdot2\cdot(2-10+2)=-24\)
    item \(2\): bin \(2\to 3\) \((10,5,5)\) \(2\cdot3\cdot(2-8+3)=-18\)
    item \(3\): bin \(1\to 3\) \((6,8,6)\) \(2\cdot4\cdot(2-10+4)=-32\)
    item \(4\): bin \(2\to 3\) \((10,3,7)\) \(2\cdot5\cdot(2-8+5)=-10\)
    item \(5\): bin \(1\to 3\) \((6,8,6)\) \(2\cdot4\cdot(2-10+4)=-32\)
    item \(6\): bin \(3\to 2\) \((10,10)\) \(2\cdot2\cdot(8-2+2)=32\) \(\leftarrow\)

    The move marked is accepted.

    Iteration 4 (move): packing patterns \(\{1,3,5\}, \{2,4,6\}\), loads \((10,10)\), \(nb=2\), \(SQ=200\). There is no feasible move.

    Iteration 5 (swap): packing patterns \(\{1,3,5\}, \{2,4,6\}\), loads \((10,10)\), \(nb=2\), \(SQ=200\). There is no feasible swap.

    \(VND\) stops with packing patterns \(\{1,3,5\}, \{2,4,6\}\): \(2=\lceil 20/10\rceil\) bins, an optimal solution. The solution of \(FF\) is a local optimum for move, the swap alone cannot change the number of bins, but the swap prepares a move that empties a bin: the local optimum depends on the neighbourhood, and combining the two neighbourhoods reaches the optimum.

Exercise 31.6: Local search BPP 3

Bins of capacity \(c=10\) and a set \(\mathscr{I}=\{1,2,3,4,5,6,7\}\) of \(7\) items with weights

\[ \begin{array}{l|ccccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} & {j=7} \\[1ex] \hline {w_j} & {5} & {3} & {3} & {2} & {8} & {4} & {4} \\ \hline \end{array} \]

The bins are labelled \(1,2,\dots\) in the order in which \(FF\) opens them, and keep their label. A move puts one item into another non-empty bin where it fits (examined for \(j=1,\dots,n\) and, for each \(j\), for increasing bin label); a swap exchanges two items \(j<k\) of different weight in different bins, if both bins stay feasible. The auxiliary objective \(SQ=\sum_b L_b^2\) is maximized; the gain of a transfer of \(\delta\) from bin \(a\) to bin \(b\) is \(2\delta(L_b-L_a+\delta)\) (a move of item \(j\) transfers \(\delta=w_j\), a swap of item \(j\) in bin \(a\) and item \(k\) in bin \(b\) transfers \(\delta=w_j-w_k\)). Best improvement breaks ties in favour of the move examined first.

Questions

  1. Compute the solution of First Fit (\(FF\)) and the lower bound \(\lceil\sum_j w_j/c\rceil\).

  2. Apply the variable neighbourhood descent with \(N_1=\) move and \(N_2=\) swap (objective \(SQ\), best improvement), starting from the solution of \(FF\).

  3. Find a packing that uses \(\lceil\sum_j w_j/c\rceil\) bins.

  4. Explain why the local search cannot reach that packing from its local optimum.

Solution

    • item \(1\) (\(w_{1}=5\)) goes into bin \(1\), opened for it, load \(5\);

    • item \(2\) (\(w_{2}=3\)) goes into bin \(1\), load \(8\);

    • item \(3\) (\(w_{3}=3\)) fits in no open bin: bin \(2\) is opened, load \(3\);

    • item \(4\) (\(w_{4}=2\)) goes into bin \(1\), load \(10\);

    • item \(5\) (\(w_{5}=8\)) fits in no open bin: bin \(3\) is opened, load \(8\);

    • item \(6\) (\(w_{6}=4\)) goes into bin \(2\), load \(7\);

    • item \(7\) (\(w_{7}=4\)) fits in no open bin: bin \(4\) is opened, load \(4\);

    \(FF\) uses \(nb=4\) bins, with packing patterns \(\{1,2,4\}, \{3,6\}, \{5\}, \{7\}\) and loads \((10,7,8,4)\). The lower bound is \(\lceil 29/10\rceil=3\).

  2. Iteration 1 (move): packing patterns \(\{1,2,4\}, \{3,6\}, \{5\}, \{7\}\), loads \((10,7,8,4)\), \(nb=4\), \(SQ=229\).

    move loads gain
    item \(1\): bin \(1\to 4\) \((5,7,8,9)\) \(2\cdot5\cdot(4-10+5)=-10\)
    item \(2\): bin \(1\to 2\) \((7,10,8,4)\) \(2\cdot3\cdot(7-10+3)=0\)
    item \(2\): bin \(1\to 4\) \((7,7,8,7)\) \(2\cdot3\cdot(4-10+3)=-18\)
    item \(3\): bin \(2\to 4\) \((10,4,8,7)\) \(2\cdot3\cdot(4-7+3)=0\)
    item \(4\): bin \(1\to 2\) \((8,9,8,4)\) \(2\cdot2\cdot(7-10+2)=-4\)
    item \(4\): bin \(1\to 3\) \((8,7,10,4)\) \(2\cdot2\cdot(8-10+2)=0\)
    item \(4\): bin \(1\to 4\) \((8,7,8,6)\) \(2\cdot2\cdot(4-10+2)=-16\)
    item \(6\): bin \(2\to 4\) \((10,3,8,8)\) \(2\cdot4\cdot(4-7+4)=8\) \(\leftarrow\)

    The move marked is accepted.

    Iteration 2 (move): packing patterns \(\{1,2,4\}, \{3\}, \{5\}, \{6,7\}\), loads \((10,3,8,8)\), \(nb=4\), \(SQ=237\).

    move loads gain
    item \(1\): bin \(1\to 2\) \((5,8,8,8)\) \(2\cdot5\cdot(3-10+5)=-20\)
    item \(2\): bin \(1\to 2\) \((7,6,8,8)\) \(2\cdot3\cdot(3-10+3)=-24\)
    item \(4\): bin \(1\to 2\) \((8,5,8,8)\) \(2\cdot2\cdot(3-10+2)=-20\)
    item \(4\): bin \(1\to 3\) \((8,3,10,8)\) \(2\cdot2\cdot(8-10+2)=0\)
    item \(4\): bin \(1\to 4\) \((8,3,8,10)\) \(2\cdot2\cdot(8-10+2)=0\)
    item \(6\): bin \(4\to 2\) \((10,7,8,4)\) \(2\cdot4\cdot(3-8+4)=-8\)
    item \(7\): bin \(4\to 2\) \((10,7,8,4)\) \(2\cdot4\cdot(3-8+4)=-8\)

    No move is improving.

    Iteration 3 (swap): packing patterns \(\{1,2,4\}, \{3\}, \{5\}, \{6,7\}\), loads \((10,3,8,8)\), \(nb=4\), \(SQ=237\).

    swap loads gain
    items \(1,3\) (bins \(1,2\)) \((8,5,8,8)\) \(2\cdot(2)\cdot(3-10+2)=-20\)
    items \(1,6\) (bins \(1,4\)) \((9,3,8,9)\) \(2\cdot(1)\cdot(8-10+1)=-2\)
    items \(1,7\) (bins \(1,4\)) \((9,3,8,9)\) \(2\cdot(1)\cdot(8-10+1)=-2\)
    items \(3,5\) (bins \(2,3\)) \((10,8,3,8)\) \(2\cdot(-5)\cdot(8-3-5)=0\)
    items \(3,6\) (bins \(2,4\)) \((10,4,8,7)\) \(2\cdot(-1)\cdot(8-3-1)=-8\)
    items \(3,7\) (bins \(2,4\)) \((10,4,8,7)\) \(2\cdot(-1)\cdot(8-3-1)=-8\)

    No swap is improving.

    \(VND\) stops with packing patterns \(\{1,2,4\}, \{3\}, \{5\}, \{6,7\}\), loads \((10,3,8,8)\), \(SQ=237\) and \(nb=4\) bins.

  3. The packing patterns \(\{1,6\}, \{4,5\}, \{2,3,7\}\), of loads \((9,10,10)\), use \(3\) bins: since \(3=\lceil 29/10\rceil\), this packing is optimal, and the local optimum is not.

  4. In the optimal packing items \(1\) and \(2\) are in different bins, while in the local optimum they are together in the full bin \(\{1,2,4\}\). To separate them, an item must leave a full bin (load \(10\)) for a lighter one: by the gain formula \(2\delta(L_b-L_a+\delta)\) such a move is improving only if \(L_b+\delta>10\), which is impossible. The auxiliary objective protects full bins, which is usually good, but here the full bin of \(FF\) is the wrong one: the search is trapped in a local optimum.

TSP: 2-opt

Exercise 31.7: Local search TSP 1

\(6\) cities with the symmetric distances

\[ \begin{array}{c|cccccc} \hline {d_{ij}} & {1} & {2} & {3} & {4} & {5} & {6} \\ \hline {1} & --- & {7} & {6} & {3} & {4} & {6} \\ {2} & {7} & --- & {6} & {5} & {7} & {4} \\ {3} & {6} & {6} & --- & {5} & {5} & {2} \\ {4} & {3} & {5} & {5} & --- & {5} & {3} \\ {5} & {4} & {7} & {5} & {5} & --- & {4} \\ {6} & {6} & {4} & {2} & {3} & {4} & --- \\ \hline \end{array} \]

A tour \(\sigma=(\sigma_1,\dots,\sigma_n)\) keeps city \(1\) in the first position. The 2-opt move \((i,j)\), for \(i=1,\dots,n-2\) and \(j=i+2,\dots,n\) (except \((1,n)\)), examined in this order, removes the edges \(\{\sigma_i,\sigma_{i+1}\}\), \(\{\sigma_j,\sigma_{j+1}\}\) (with \(\sigma_{n+1}=\sigma_1\)), reverses \(\sigma_{i+1},\dots,\sigma_j\), and changes the length by \(\Delta=d_{\sigma_i\sigma_j}+d_{\sigma_{i+1}\sigma_{j+1}}-d_{\sigma_i\sigma_{i+1}}-d_{\sigma_j\sigma_{j+1}}\). Best improvement breaks ties in favour of the move examined first. The nearest neighbour heuristic \(NN\) breaks ties in favour of the city of smallest index.

Questions

  1. Compute the tour of \(NN\) from city \(1\) and its length.

  2. Compute \(\Delta\) for all the 2-opt moves of the tour of \(NN\), and check one of them by computing the length of the new tour directly.

  3. Apply the 2-opt local search with the best-improvement rule, starting from the tour of \(NN\).

  4. The optimal value is \(z(I)=23\). Is the final tour optimal? How many moves were made, compared with the bound \(L(\sigma^0)-z(I)\) on the number of moves?

Solution

    • from city \(1\) the nearest unvisited city is \(4\) (\(d_{1,4}=3\));

    • from city \(4\) the nearest unvisited city is \(6\) (\(d_{4,6}=3\));

    • from city \(6\) the nearest unvisited city is \(3\) (\(d_{6,3}=2\));

    • from city \(3\) the nearest unvisited city is \(5\) (\(d_{3,5}=5\));

    • from city \(5\) the nearest unvisited city is \(2\) (\(d_{5,2}=7\));

    • the tour goes back to city \(1\) (\(d_{2,1}=7\)).

    The tour is \(\sigma=(1,4,6,3,5,2)\), of length \(27\).

  2. The \(9\) moves of the tour of \(NN\) are

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,4\},\{6,3\}\) \(6+5-3-2=+6\) \((1,6,4,3,5,2)\) \(33\)
    \((1,4)\) \(\{1,4\},\{3,5\}\) \(6+5-3-5=+3\) \((1,3,6,4,5,2)\) \(30\)
    \((1,5)\) \(\{1,4\},\{5,2\}\) \(4+5-3-7=-1\) \((1,5,3,6,4,2)\) \(26\)
    \((2,4)\) \(\{4,6\},\{3,5\}\) \(5+4-3-5=+1\) \((1,4,3,6,5,2)\) \(28\)
    \((2,5)\) \(\{4,6\},\{5,2\}\) \(5+4-3-7=-1\) \((1,4,5,3,6,2)\) \(26\)
    \((2,6)\) \(\{4,6\},\{2,1\}\) \(5+6-3-7=+1\) \((1,4,2,5,3,6)\) \(28\)
    \((3,5)\) \(\{6,3\},\{5,2\}\) \(4+6-2-7=+1\) \((1,4,6,5,3,2)\) \(28\)
    \((3,6)\) \(\{6,3\},\{2,1\}\) \(4+6-2-7=+1\) \((1,4,6,2,5,3)\) \(28\)
    \((4,6)\) \(\{3,5\},\{2,1\}\) \(6+4-5-7=-2\) \((1,4,6,3,2,5)\) \(25\)

    For example, the move \((1,3)\) gives the tour \((1,6,4,3,5,2)\), of length \(6+3+5+5+7+7=33=27+6\).

  3. Iteration 1: \(\sigma=(1,4,6,3,5,2)\), length \(27\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,4\},\{6,3\}\) \(6+5-3-2=+6\) \((1,6,4,3,5,2)\) \(33\)
    \((1,4)\) \(\{1,4\},\{3,5\}\) \(6+5-3-5=+3\) \((1,3,6,4,5,2)\) \(30\)
    \((1,5)\) \(\{1,4\},\{5,2\}\) \(4+5-3-7=-1\) \((1,5,3,6,4,2)\) \(26\)
    \((2,4)\) \(\{4,6\},\{3,5\}\) \(5+4-3-5=+1\) \((1,4,3,6,5,2)\) \(28\)
    \((2,5)\) \(\{4,6\},\{5,2\}\) \(5+4-3-7=-1\) \((1,4,5,3,6,2)\) \(26\)
    \((2,6)\) \(\{4,6\},\{2,1\}\) \(5+6-3-7=+1\) \((1,4,2,5,3,6)\) \(28\)
    \((3,5)\) \(\{6,3\},\{5,2\}\) \(4+6-2-7=+1\) \((1,4,6,5,3,2)\) \(28\)
    \((3,6)\) \(\{6,3\},\{2,1\}\) \(4+6-2-7=+1\) \((1,4,6,2,5,3)\) \(28\)
    \((4,6)\) \(\{3,5\},\{2,1\}\) \(6+4-5-7=-2\) \((1,4,6,3,2,5)\) \(25\) \(\leftarrow\)

    The move \((4,6)\) is accepted after 9 evaluations.

    Iteration 2: \(\sigma=(1,4,6,3,2,5)\), length \(25\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,4\},\{6,3\}\) \(6+5-3-2=+6\) \((1,6,4,3,2,5)\) \(31\)
    \((1,4)\) \(\{1,4\},\{3,2\}\) \(6+5-3-6=+2\) \((1,3,6,4,2,5)\) \(27\)
    \((1,5)\) \(\{1,4\},\{2,5\}\) \(7+5-3-7=+2\) \((1,2,3,6,4,5)\) \(27\)
    \((2,4)\) \(\{4,6\},\{3,2\}\) \(5+4-3-6=0\) \((1,4,3,6,2,5)\) \(25\)
    \((2,5)\) \(\{4,6\},\{2,5\}\) \(5+4-3-7=-1\) \((1,4,2,3,6,5)\) \(24\) \(\leftarrow\)
    \((2,6)\) \(\{4,6\},\{5,1\}\) \(5+6-3-4=+4\) \((1,4,5,2,3,6)\) \(29\)
    \((3,5)\) \(\{6,3\},\{2,5\}\) \(4+5-2-7=0\) \((1,4,6,2,3,5)\) \(25\)
    \((3,6)\) \(\{6,3\},\{5,1\}\) \(4+6-2-4=+4\) \((1,4,6,5,2,3)\) \(29\)
    \((4,6)\) \(\{3,2\},\{5,1\}\) \(5+7-6-4=+2\) \((1,4,6,3,5,2)\) \(27\)

    The move \((2,5)\) is accepted after 9 evaluations.

    Iteration 3: \(\sigma=(1,4,2,3,6,5)\), length \(24\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,4\},\{2,3\}\) \(7+5-3-6=+3\) \((1,2,4,3,6,5)\) \(27\)
    \((1,4)\) \(\{1,4\},\{3,6\}\) \(6+3-3-2=+4\) \((1,3,2,4,6,5)\) \(28\)
    \((1,5)\) \(\{1,4\},\{6,5\}\) \(6+5-3-4=+4\) \((1,6,3,2,4,5)\) \(28\)
    \((2,4)\) \(\{4,2\},\{3,6\}\) \(5+4-5-2=+2\) \((1,4,3,2,6,5)\) \(26\)
    \((2,5)\) \(\{4,2\},\{6,5\}\) \(3+7-5-4=+1\) \((1,4,6,3,2,5)\) \(25\)
    \((2,6)\) \(\{4,2\},\{5,1\}\) \(5+7-5-4=+3\) \((1,4,5,6,3,2)\) \(27\)
    \((3,5)\) \(\{2,3\},\{6,5\}\) \(4+5-6-4=-1\) \((1,4,2,6,3,5)\) \(23\) \(\leftarrow\)
    \((3,6)\) \(\{2,3\},\{5,1\}\) \(7+6-6-4=+3\) \((1,4,2,5,6,3)\) \(27\)
    \((4,6)\) \(\{3,6\},\{5,1\}\) \(5+6-2-4=+5\) \((1,4,2,3,5,6)\) \(29\)

    The move \((3,5)\) is accepted after 9 evaluations.

    Iteration 4: \(\sigma=(1,4,2,6,3,5)\), length \(23\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,4\},\{2,6\}\) \(7+3-3-4=+3\) \((1,2,4,6,3,5)\) \(26\)
    \((1,4)\) \(\{1,4\},\{6,3\}\) \(6+5-3-2=+6\) \((1,6,2,4,3,5)\) \(29\)
    \((1,5)\) \(\{1,4\},\{3,5\}\) \(6+5-3-5=+3\) \((1,3,6,2,4,5)\) \(26\)
    \((2,4)\) \(\{4,2\},\{6,3\}\) \(3+6-5-2=+2\) \((1,4,6,2,3,5)\) \(25\)
    \((2,5)\) \(\{4,2\},\{3,5\}\) \(5+7-5-5=+2\) \((1,4,3,6,2,5)\) \(25\)
    \((2,6)\) \(\{4,2\},\{5,1\}\) \(5+7-5-4=+3\) \((1,4,5,3,6,2)\) \(26\)
    \((3,5)\) \(\{2,6\},\{3,5\}\) \(6+4-4-5=+1\) \((1,4,2,3,6,5)\) \(24\)
    \((3,6)\) \(\{2,6\},\{5,1\}\) \(7+6-4-4=+5\) \((1,4,2,5,3,6)\) \(28\)
    \((4,6)\) \(\{6,3\},\{5,1\}\) \(4+6-2-4=+4\) \((1,4,2,6,5,3)\) \(27\)

    No move has \(\Delta<0\): \(\sigma=(1,4,2,6,3,5)\) is a 2-opt local optimum (9 evaluations).

    The search makes 3 moves: \(27\to25\to24\to23\).

  4. The final tour has length \(23=z(I)\): it is optimal. The search made 3 moves, while the termination property of the notes allows at most \(27-23=4\).

Exercise 31.8: Local search TSP 2

\(6\) cities with the symmetric distances

\[ \begin{array}{c|cccccc} \hline {d_{ij}} & {1} & {2} & {3} & {4} & {5} & {6} \\ \hline {1} & --- & {8} & {5} & {6} & {5} & {6} \\ {2} & {8} & --- & {6} & {7} & {7} & {6} \\ {3} & {5} & {6} & --- & {4} & {8} & {2} \\ {4} & {6} & {7} & {4} & --- & {6} & {5} \\ {5} & {5} & {7} & {8} & {6} & --- & {7} \\ {6} & {6} & {6} & {2} & {5} & {7} & --- \\ \hline \end{array} \]

A tour \(\sigma=(\sigma_1,\dots,\sigma_n)\) keeps city \(1\) in the first position. The 2-opt move \((i,j)\), for \(i=1,\dots,n-2\) and \(j=i+2,\dots,n\) (except \((1,n)\)), examined in this order, removes the edges \(\{\sigma_i,\sigma_{i+1}\}\), \(\{\sigma_j,\sigma_{j+1}\}\) (with \(\sigma_{n+1}=\sigma_1\)), reverses \(\sigma_{i+1},\dots,\sigma_j\), and changes the length by \(\Delta=d_{\sigma_i\sigma_j}+d_{\sigma_{i+1}\sigma_{j+1}}-d_{\sigma_i\sigma_{i+1}}-d_{\sigma_j\sigma_{j+1}}\). Best improvement breaks ties in favour of the move examined first. The nearest neighbour heuristic \(NN\) breaks ties in favour of the city of smallest index.

Questions

  1. Compute the tour of \(NN\) from city \(1\) and its length.

  2. Apply the 2-opt local search with the first-improvement rule, starting from the tour of \(NN\).

  3. Apply the 2-opt local search with the best-improvement rule, starting from the tour of \(NN\).

  4. The optimal value is \(z(I)=30\). Compare the two local optima and the number of evaluations of the two rules.

Solution

    • from city \(1\) the nearest unvisited city is \(3\) (\(d_{1,3}=5\));

    • from city \(3\) the nearest unvisited city is \(6\) (\(d_{3,6}=2\));

    • from city \(6\) the nearest unvisited city is \(4\) (\(d_{6,4}=5\));

    • from city \(4\) the nearest unvisited city is \(5\) (\(d_{4,5}=6\));

    • from city \(5\) the nearest unvisited city is \(2\) (\(d_{5,2}=7\));

    • the tour goes back to city \(1\) (\(d_{2,1}=8\)).

    The tour is \(\sigma=(1,3,6,4,5,2)\), of length \(33\).

  2. Iteration 1: \(\sigma=(1,3,6,4,5,2)\), length \(33\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,3\},\{6,4\}\) \(6+4-5-5=0\) \((1,6,3,4,5,2)\) \(33\)
    \((1,4)\) \(\{1,3\},\{4,5\}\) \(6+8-5-6=+3\) \((1,4,6,3,5,2)\) \(36\)
    \((1,5)\) \(\{1,3\},\{5,2\}\) \(5+6-5-7=-1\) \((1,5,4,6,3,2)\) \(32\) \(\leftarrow\)
    \((2,4)\) \(\{3,6\},\{4,5\}\) \(4+7-2-6=+3\) \((1,3,4,6,5,2)\) \(36\)
    \((2,5)\) \(\{3,6\},\{5,2\}\) \(8+6-2-7=+5\) \((1,3,5,4,6,2)\) \(38\)
    \((2,6)\) \(\{3,6\},\{2,1\}\) \(6+6-2-8=+2\) \((1,3,2,5,4,6)\) \(35\)
    \((3,5)\) \(\{6,4\},\{5,2\}\) \(7+7-5-7=+2\) \((1,3,6,5,4,2)\) \(35\)
    \((3,6)\) \(\{6,4\},\{2,1\}\) \(6+6-5-8=-1\) \((1,3,6,2,5,4)\) \(32\)
    \((4,6)\) \(\{4,5\},\{2,1\}\) \(7+5-6-8=-2\) \((1,3,6,4,2,5)\) \(31\)

    The move \((1,5)\) is accepted after 3 evaluations.

    Iteration 2: \(\sigma=(1,5,4,6,3,2)\), length \(32\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,5\},\{4,6\}\) \(6+7-5-5=+3\) \((1,4,5,6,3,2)\) \(35\)
    \((1,4)\) \(\{1,5\},\{6,3\}\) \(6+8-5-2=+7\) \((1,6,4,5,3,2)\) \(39\)
    \((1,5)\) \(\{1,5\},\{3,2\}\) \(5+7-5-6=+1\) \((1,3,6,4,5,2)\) \(33\)
    \((2,4)\) \(\{5,4\},\{6,3\}\) \(7+4-6-2=+3\) \((1,5,6,4,3,2)\) \(35\)
    \((2,5)\) \(\{5,4\},\{3,2\}\) \(8+7-6-6=+3\) \((1,5,3,6,4,2)\) \(35\)
    \((2,6)\) \(\{5,4\},\{2,1\}\) \(7+6-6-8=-1\) \((1,5,2,3,6,4)\) \(31\) \(\leftarrow\)
    \((3,5)\) \(\{4,6\},\{3,2\}\) \(4+6-5-6=-1\) \((1,5,4,3,6,2)\) \(31\)
    \((3,6)\) \(\{4,6\},\{2,1\}\) \(7+6-5-8=0\) \((1,5,4,2,3,6)\) \(32\)
    \((4,6)\) \(\{6,3\},\{2,1\}\) \(6+5-2-8=+1\) \((1,5,4,6,2,3)\) \(33\)

    The move \((2,6)\) is accepted after 6 evaluations.

    Iteration 3: \(\sigma=(1,5,2,3,6,4)\), length \(31\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,5\},\{2,3\}\) \(8+8-5-6=+5\) \((1,2,5,3,6,4)\) \(36\)
    \((1,4)\) \(\{1,5\},\{3,6\}\) \(5+7-5-2=+5\) \((1,3,2,5,6,4)\) \(36\)
    \((1,5)\) \(\{1,5\},\{6,4\}\) \(6+6-5-5=+2\) \((1,6,3,2,5,4)\) \(33\)
    \((2,4)\) \(\{5,2\},\{3,6\}\) \(8+6-7-2=+5\) \((1,5,3,2,6,4)\) \(36\)
    \((2,5)\) \(\{5,2\},\{6,4\}\) \(7+7-7-5=+2\) \((1,5,6,3,2,4)\) \(33\)
    \((2,6)\) \(\{5,2\},\{4,1\}\) \(6+8-7-6=+1\) \((1,5,4,6,3,2)\) \(32\)
    \((3,5)\) \(\{2,3\},\{6,4\}\) \(6+4-6-5=-1\) \((1,5,2,6,3,4)\) \(30\) \(\leftarrow\)
    \((3,6)\) \(\{2,3\},\{4,1\}\) \(7+5-6-6=0\) \((1,5,2,4,6,3)\) \(31\)
    \((4,6)\) \(\{3,6\},\{4,1\}\) \(4+6-2-6=+2\) \((1,5,2,3,4,6)\) \(33\)

    The move \((3,5)\) is accepted after 7 evaluations.

    Iteration 4: \(\sigma=(1,5,2,6,3,4)\), length \(30\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,5\},\{2,6\}\) \(8+7-5-6=+4\) \((1,2,5,6,3,4)\) \(34\)
    \((1,4)\) \(\{1,5\},\{6,3\}\) \(6+8-5-2=+7\) \((1,6,2,5,3,4)\) \(37\)
    \((1,5)\) \(\{1,5\},\{3,4\}\) \(5+6-5-4=+2\) \((1,3,6,2,5,4)\) \(32\)
    \((2,4)\) \(\{5,2\},\{6,3\}\) \(7+6-7-2=+4\) \((1,5,6,2,3,4)\) \(34\)
    \((2,5)\) \(\{5,2\},\{3,4\}\) \(8+7-7-4=+4\) \((1,5,3,6,2,4)\) \(34\)
    \((2,6)\) \(\{5,2\},\{4,1\}\) \(6+8-7-6=+1\) \((1,5,4,3,6,2)\) \(31\)
    \((3,5)\) \(\{2,6\},\{3,4\}\) \(6+5-6-4=+1\) \((1,5,2,3,6,4)\) \(31\)
    \((3,6)\) \(\{2,6\},\{4,1\}\) \(7+6-6-6=+1\) \((1,5,2,4,3,6)\) \(31\)
    \((4,6)\) \(\{6,3\},\{4,1\}\) \(5+5-2-6=+2\) \((1,5,2,6,4,3)\) \(32\)

    No move has \(\Delta<0\): \(\sigma=(1,5,2,6,3,4)\) is a 2-opt local optimum (9 evaluations).

    First improvement makes 3 moves, \(33\to32\to31\to30\), with 25 evaluations in total.

  3. Iteration 1: \(\sigma=(1,3,6,4,5,2)\), length \(33\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,3\},\{6,4\}\) \(6+4-5-5=0\) \((1,6,3,4,5,2)\) \(33\)
    \((1,4)\) \(\{1,3\},\{4,5\}\) \(6+8-5-6=+3\) \((1,4,6,3,5,2)\) \(36\)
    \((1,5)\) \(\{1,3\},\{5,2\}\) \(5+6-5-7=-1\) \((1,5,4,6,3,2)\) \(32\)
    \((2,4)\) \(\{3,6\},\{4,5\}\) \(4+7-2-6=+3\) \((1,3,4,6,5,2)\) \(36\)
    \((2,5)\) \(\{3,6\},\{5,2\}\) \(8+6-2-7=+5\) \((1,3,5,4,6,2)\) \(38\)
    \((2,6)\) \(\{3,6\},\{2,1\}\) \(6+6-2-8=+2\) \((1,3,2,5,4,6)\) \(35\)
    \((3,5)\) \(\{6,4\},\{5,2\}\) \(7+7-5-7=+2\) \((1,3,6,5,4,2)\) \(35\)
    \((3,6)\) \(\{6,4\},\{2,1\}\) \(6+6-5-8=-1\) \((1,3,6,2,5,4)\) \(32\)
    \((4,6)\) \(\{4,5\},\{2,1\}\) \(7+5-6-8=-2\) \((1,3,6,4,2,5)\) \(31\) \(\leftarrow\)

    The move \((4,6)\) is accepted after 9 evaluations.

    Iteration 2: \(\sigma=(1,3,6,4,2,5)\), length \(31\).

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,3\},\{6,4\}\) \(6+4-5-5=0\) \((1,6,3,4,2,5)\) \(31\)
    \((1,4)\) \(\{1,3\},\{4,2\}\) \(6+6-5-7=0\) \((1,4,6,3,2,5)\) \(31\)
    \((1,5)\) \(\{1,3\},\{2,5\}\) \(8+8-5-7=+4\) \((1,2,4,6,3,5)\) \(35\)
    \((2,4)\) \(\{3,6\},\{4,2\}\) \(4+6-2-7=+1\) \((1,3,4,6,2,5)\) \(32\)
    \((2,5)\) \(\{3,6\},\{2,5\}\) \(6+7-2-7=+4\) \((1,3,2,4,6,5)\) \(35\)
    \((2,6)\) \(\{3,6\},\{5,1\}\) \(8+6-2-5=+7\) \((1,3,5,2,4,6)\) \(38\)
    \((3,5)\) \(\{6,4\},\{2,5\}\) \(6+6-5-7=0\) \((1,3,6,2,4,5)\) \(31\)
    \((3,6)\) \(\{6,4\},\{5,1\}\) \(7+6-5-5=+3\) \((1,3,6,5,2,4)\) \(34\)
    \((4,6)\) \(\{4,2\},\{5,1\}\) \(6+8-7-5=+2\) \((1,3,6,4,5,2)\) \(33\)

    No move has \(\Delta<0\): \(\sigma=(1,3,6,4,2,5)\) is a 2-opt local optimum (9 evaluations).

    Best improvement makes 1 move, \(33\to31\), with 18 evaluations in total.

  4. First improvement reaches a tour of length \(30=z(I)\), an optimal tour, while best improvement stops in a local optimum of length \(31\), \(3.3\%\) above the optimum. The steepest first move (\(\Delta=-2\)) leads into a worse valley: best improvement is not always better than first improvement. First improvement examines 25 moves in total, best improvement 18: the better local optimum costs more evaluations here, because first improvement makes more moves.

Exercise 31.9: Local search TSP 3

\(6\) cities with the symmetric distances

\[ \begin{array}{c|cccccc} \hline {d_{ij}} & {1} & {2} & {3} & {4} & {5} & {6} \\ \hline {1} & --- & {7} & {8} & {8} & {9} & {9} \\ {2} & {7} & --- & {7} & {4} & {9} & {8} \\ {3} & {8} & {7} & --- & {7} & {3} & {9} \\ {4} & {8} & {4} & {7} & --- & {5} & {6} \\ {5} & {9} & {9} & {3} & {5} & --- & {7} \\ {6} & {9} & {8} & {9} & {6} & {7} & --- \\ \hline \end{array} \]

A tour \(\sigma=(\sigma_1,\dots,\sigma_n)\) keeps city \(1\) in the first position. The 2-opt move \((i,j)\), for \(i=1,\dots,n-2\) and \(j=i+2,\dots,n\) (except \((1,n)\)), examined in this order, removes the edges \(\{\sigma_i,\sigma_{i+1}\}\), \(\{\sigma_j,\sigma_{j+1}\}\) (with \(\sigma_{n+1}=\sigma_1\)), reverses \(\sigma_{i+1},\dots,\sigma_j\), and changes the length by \(\Delta=d_{\sigma_i\sigma_j}+d_{\sigma_{i+1}\sigma_{j+1}}-d_{\sigma_i\sigma_{i+1}}-d_{\sigma_j\sigma_{j+1}}\). Best improvement breaks ties in favour of the move examined first. The nearest neighbour heuristic \(NN\) breaks ties in favour of the city of smallest index. An Or-opt move with \(\ell=1\) takes one city \(\sigma_i\) (\(i\ge 2\)) and inserts it between two consecutive cities \(\sigma_k,\sigma_{k+1}\) not adjacent to it (\(k\ne i-1,i\)); with \(p=\sigma_{i-1}\), \(q=\sigma_{i+1}\), \(s=\sigma_i\), \(a=\sigma_k\), \(b=\sigma_{k+1}\) it changes the length by \(\Delta=d_{pq}+d_{as}+d_{sb}-d_{ps}-d_{sq}-d_{ab}\). The moves are examined for \(i=2,\dots,n\) and \(k=1,\dots,n\).

Questions

  1. Compute the tour of \(NN\) from city \(1\) and its length.

  2. Show that the tour of \(NN\) is a 2-opt local optimum.

  3. Apply one iteration of best improvement with the Or-opt moves with \(\ell=1\) to the tour of \(NN\).

  4. The optimal value is \(z(I)=35\). Is the new tour optimal? Is it a 2-opt local optimum? What does this show about combining the two neighbourhoods?

Solution

    • from city \(1\) the nearest unvisited city is \(2\) (\(d_{1,2}=7\));

    • from city \(2\) the nearest unvisited city is \(4\) (\(d_{2,4}=4\));

    • from city \(4\) the nearest unvisited city is \(5\) (\(d_{4,5}=5\));

    • from city \(5\) the nearest unvisited city is \(3\) (\(d_{5,3}=3\));

    • from city \(3\) the nearest unvisited city is \(6\) (\(d_{3,6}=9\));

    • the tour goes back to city \(1\) (\(d_{6,1}=9\)).

    The tour is \(\sigma=(1,2,4,5,3,6)\), of length \(37\).

  2. The 2-opt moves of the tour of \(NN\) are

    \((i,j)\) removed edges \(\Delta\) new tour length
    \((1,3)\) \(\{1,2\},\{4,5\}\) \(8+9-7-5=+5\) \((1,4,2,5,3,6)\) \(42\)
    \((1,4)\) \(\{1,2\},\{5,3\}\) \(9+7-7-3=+6\) \((1,5,4,2,3,6)\) \(43\)
    \((1,5)\) \(\{1,2\},\{3,6\}\) \(8+8-7-9=0\) \((1,3,5,4,2,6)\) \(37\)
    \((2,4)\) \(\{2,4\},\{5,3\}\) \(9+7-4-3=+9\) \((1,2,5,4,3,6)\) \(46\)
    \((2,5)\) \(\{2,4\},\{3,6\}\) \(7+6-4-9=0\) \((1,2,3,5,4,6)\) \(37\)
    \((2,6)\) \(\{2,4\},\{6,1\}\) \(8+8-4-9=+3\) \((1,2,6,3,5,4)\) \(40\)
    \((3,5)\) \(\{4,5\},\{3,6\}\) \(7+7-5-9=0\) \((1,2,4,3,5,6)\) \(37\)
    \((3,6)\) \(\{4,5\},\{6,1\}\) \(6+9-5-9=+1\) \((1,2,4,6,3,5)\) \(38\)
    \((4,6)\) \(\{5,3\},\{6,1\}\) \(7+8-3-9=+3\) \((1,2,4,5,6,3)\) \(40\)

    All the moves have \(\Delta\ge 0\): the tour of \(NN\) is a 2-opt local optimum.

  3. The Or-opt moves with \(\ell=1\) of the tour of \(NN\) are

    city \(s\) between \(\Delta\) length
    \(2\) \(4,5\) \(8+4+9-7-4-5=+5\) \(42\)
    \(2\) \(5,3\) \(8+9+7-7-4-3=+10\) \(47\)
    \(2\) \(3,6\) \(8+7+8-7-4-9=+3\) \(40\)
    \(2\) \(6,1\) \(8+8+7-7-4-9=+3\) \(40\)
    \(4\) \(1,2\) \(9+8+4-4-5-7=+5\) \(42\)
    \(4\) \(5,3\) \(9+5+7-4-5-3=+9\) \(46\)
    \(4\) \(3,6\) \(9+7+6-4-5-9=+4\) \(41\)
    \(4\) \(6,1\) \(9+6+8-4-5-9=+5\) \(42\)
    \(5\) \(1,2\) \(7+9+9-5-3-7=+10\) \(47\)
    \(5\) \(2,4\) \(7+9+5-5-3-4=+9\) \(46\)
    \(5\) \(3,6\) \(7+3+7-5-3-9=0\) \(37\)
    \(5\) \(6,1\) \(7+7+9-5-3-9=+6\) \(43\)
    \(3\) \(1,2\) \(7+8+7-3-9-7=+3\) \(40\)
    \(3\) \(2,4\) \(7+7+7-3-9-4=+5\) \(42\)
    \(3\) \(4,5\) \(7+7+3-3-9-5=0\) \(37\)
    \(3\) \(6,1\) \(7+9+8-3-9-9=+3\) \(40\)
    \(6\) \(1,2\) \(8+9+8-9-9-7=0\) \(37\)
    \(6\) \(2,4\) \(8+8+6-9-9-4=0\) \(37\)
    \(6\) \(4,5\) \(8+6+7-9-9-5=-2\) \(35\) \(\leftarrow\)
    \(6\) \(5,3\) \(8+7+9-9-9-3=+3\) \(40\)

    The best move inserts city \(6\) between cities \(4\) and \(5\), with \(\Delta=-2\): the new tour is \((1,2,4,6,5,3)\), of length \(35\).

  4. The new tour has length \(35=z(I)\): it is optimal, hence also a 2-opt local optimum. The tour of \(NN\) is a local optimum for 2-opt but not for Or-opt: a variable neighbourhood descent with \(N_1=\) 2-opt and \(N_2=\) Or-opt would stop only in a tour that is a local optimum for both, and here it finds the optimum.

\(P\|C_{\max}\)

Exercise 31.10: Local search \(P\,||\,C_{\max}\) 1

\(m=3\) identical machines and \(6\) jobs with processing times

\[ \begin{array}{l|cccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\[1ex] \hline {t_j} & {5} & {7} & {3} & {4} & {4} & {9} \\ \hline \end{array} \]

A move reassigns one job \(j\) to another machine \(h\) (examined for \(j=1,\dots,n\) and \(h=1,\dots,m\)); a swap exchanges the machines of two jobs \(j<k\) on different machines with \(t_j\ne t_k\). The local searches use the best-improvement rule, with ties broken in favour of the move examined first.

Questions

  1. Compute the schedule of list scheduling (\(LIST\)) with the jobs in the order \(1,2,\dots,n\), and its makespan.

  2. Apply the move local search with the makespan as objective, starting from the schedule of \(LIST\).

  3. Compute the lower bound \(\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}\).

  4. Prove that the final schedule is optimal.

Solution

    • job \(1\) (\(t_{1}=5\)) goes to machine \(1\), the least loaded (load \(0\)), which reaches \(5\);

    • job \(2\) (\(t_{2}=7\)) goes to machine \(2\), the least loaded (load \(0\)), which reaches \(7\);

    • job \(3\) (\(t_{3}=3\)) goes to machine \(3\), the least loaded (load \(0\)), which reaches \(3\);

    • job \(4\) (\(t_{4}=4\)) goes to machine \(3\), the least loaded (load \(3\)), which reaches \(7\);

    • job \(5\) (\(t_{5}=4\)) goes to machine \(1\), the least loaded (load \(5\)), which reaches \(9\);

    • job \(6\) (\(t_{6}=9\)) goes to machine \(2\), the least loaded (load \(7\)), which reaches \(16\);

    The schedule is \(J_{1}=\{1,5\}, J_{2}=\{2,6\}, J_{3}=\{3,4\}\), with loads \((9,16,7)\) and \(C_{\max}=16\).

  2. Iteration 1: \(J_{1}=\{1,5\}, J_{2}=\{2,6\}, J_{3}=\{3,4\}\), loads \((9,16,7)\), \(C_{\max}=16\).

    move loads \(C_{\max}\)
    job \(1\): \(M_1\to M_2\) \((4,21,7)\) \(21\)
    job \(1\): \(M_1\to M_3\) \((4,16,12)\) \(16\)
    job \(2\): \(M_2\to M_1\) \((16,9,7)\) \(16\)
    job \(2\): \(M_2\to M_3\) \((9,9,14)\) \(14\) \(\leftarrow\)
    job \(3\): \(M_3\to M_1\) \((12,16,4)\) \(16\)
    job \(3\): \(M_3\to M_2\) \((9,19,4)\) \(19\)
    job \(4\): \(M_3\to M_1\) \((13,16,3)\) \(16\)
    job \(4\): \(M_3\to M_2\) \((9,20,3)\) \(20\)
    job \(5\): \(M_1\to M_2\) \((5,20,7)\) \(20\)
    job \(5\): \(M_1\to M_3\) \((5,16,11)\) \(16\)
    job \(6\): \(M_2\to M_1\) \((18,7,7)\) \(18\)
    job \(6\): \(M_2\to M_3\) \((9,7,16)\) \(16\)

    The move marked is accepted.

    Iteration 2: \(J_{1}=\{1,5\}, J_{2}=\{6\}, J_{3}=\{2,3,4\}\), loads \((9,9,14)\), \(C_{\max}=14\).

    move loads \(C_{\max}\)
    job \(1\): \(M_1\to M_2\) \((4,14,14)\) \(14\)
    job \(1\): \(M_1\to M_3\) \((4,9,19)\) \(19\)
    job \(2\): \(M_3\to M_1\) \((16,9,7)\) \(16\)
    job \(2\): \(M_3\to M_2\) \((9,16,7)\) \(16\)
    job \(3\): \(M_3\to M_1\) \((12,9,11)\) \(12\) \(\leftarrow\)
    job \(3\): \(M_3\to M_2\) \((9,12,11)\) \(12\)
    job \(4\): \(M_3\to M_1\) \((13,9,10)\) \(13\)
    job \(4\): \(M_3\to M_2\) \((9,13,10)\) \(13\)
    job \(5\): \(M_1\to M_2\) \((5,13,14)\) \(14\)
    job \(5\): \(M_1\to M_3\) \((5,9,18)\) \(18\)
    job \(6\): \(M_2\to M_1\) \((18,0,14)\) \(18\)
    job \(6\): \(M_2\to M_3\) \((9,0,23)\) \(23\)

    The move marked is accepted.

    Iteration 3: \(J_{1}=\{1,3,5\}, J_{2}=\{6\}, J_{3}=\{2,4\}\), loads \((12,9,11)\), \(C_{\max}=12\).

    move loads \(C_{\max}\)
    job \(1\): \(M_1\to M_2\) \((7,14,11)\) \(14\)
    job \(1\): \(M_1\to M_3\) \((7,9,16)\) \(16\)
    job \(2\): \(M_3\to M_1\) \((19,9,4)\) \(19\)
    job \(2\): \(M_3\to M_2\) \((12,16,4)\) \(16\)
    job \(3\): \(M_1\to M_2\) \((9,12,11)\) \(12\)
    job \(3\): \(M_1\to M_3\) \((9,9,14)\) \(14\)
    job \(4\): \(M_3\to M_1\) \((16,9,7)\) \(16\)
    job \(4\): \(M_3\to M_2\) \((12,13,7)\) \(13\)
    job \(5\): \(M_1\to M_2\) \((8,13,11)\) \(13\)
    job \(5\): \(M_1\to M_3\) \((8,9,15)\) \(15\)
    job \(6\): \(M_2\to M_1\) \((21,0,11)\) \(21\)
    job \(6\): \(M_2\to M_3\) \((12,0,20)\) \(20\)

    No move is improving: local optimum.

    The search makes 2 moves, \(16\to14\to12\), and stops in \(J_{1}=\{1,3,5\}, J_{2}=\{6\}, J_{3}=\{2,4\}\).

  3. The bound is \(\max\{9,\lceil 32/3\rceil\}=11\).

  4. The bound \(11\) is not attained, but a makespan of \(11\) is impossible. Job \(6\) (\(t_{6}=9\)) can share its machine only with jobs of total time at most \(11-9=2\), and every other job has \(t_j\ge 3\): its machine contains job \(6\) only. The other \(5\) jobs, of total time \(32-9=23\), should fit on two machines of load at most \(11\), i.e., at most \(22\): impossible. Hence \(z(I)\ge 12\), and the final schedule, with \(C_{\max}=12\), is optimal.

Exercise 31.11: Local search \(P\,||\,C_{\max}\) 2

\(m=3\) identical machines and \(7\) jobs with processing times

\[ \begin{array}{l|ccccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} & {j=7} \\[1ex] \hline {t_j} & {8} & {4} & {6} & {7} & {5} & {9} & {8} \\ \hline \end{array} \]

A move reassigns one job \(j\) to another machine \(h\) (examined for \(j=1,\dots,n\) and \(h=1,\dots,m\)); a swap exchanges the machines of two jobs \(j<k\) on different machines with \(t_j\ne t_k\). The local searches use the best-improvement rule, with ties broken in favour of the move examined first.

Questions

  1. Compute the schedule of \(LPT\) (ties broken by the smallest index) and its makespan.

  2. Show that the schedule of \(LPT\) is a local optimum for the move neighbourhood.

  3. Apply the swap local search with the makespan as objective, starting from the schedule of \(LPT\).

  4. Compute the lower bound \(\lceil\sum_j t_j/m\rceil\) and conclude. What does the exercise show?

Solution

  1. The jobs by non-increasing time are \((6,1,7,4,3,5,2)\).

    • job \(6\) (\(t_{6}=9\)) goes to machine \(1\), the least loaded (load \(0\)), which reaches \(9\);

    • job \(1\) (\(t_{1}=8\)) goes to machine \(2\), the least loaded (load \(0\)), which reaches \(8\);

    • job \(7\) (\(t_{7}=8\)) goes to machine \(3\), the least loaded (load \(0\)), which reaches \(8\);

    • job \(4\) (\(t_{4}=7\)) goes to machine \(2\), the least loaded (load \(8\)), which reaches \(15\);

    • job \(3\) (\(t_{3}=6\)) goes to machine \(3\), the least loaded (load \(8\)), which reaches \(14\);

    • job \(5\) (\(t_{5}=5\)) goes to machine \(1\), the least loaded (load \(9\)), which reaches \(14\);

    • job \(2\) (\(t_{2}=4\)) goes to machine \(1\), the least loaded (load \(14\)), which reaches \(18\);

    The schedule is \(J_{1}=\{2,5,6\}, J_{2}=\{1,4\}, J_{3}=\{3,7\}\), with loads \((18,15,14)\) and \(C_{\max}=18\).

  2. Iteration 1: \(J_{1}=\{2,5,6\}, J_{2}=\{1,4\}, J_{3}=\{3,7\}\), loads \((18,15,14)\), \(C_{\max}=18\).

    move loads \(C_{\max}\)
    job \(1\): \(M_2\to M_1\) \((26,7,14)\) \(26\)
    job \(1\): \(M_2\to M_3\) \((18,7,22)\) \(22\)
    job \(2\): \(M_1\to M_2\) \((14,19,14)\) \(19\)
    job \(2\): \(M_1\to M_3\) \((14,15,18)\) \(18\)
    job \(3\): \(M_3\to M_1\) \((24,15,8)\) \(24\)
    job \(3\): \(M_3\to M_2\) \((18,21,8)\) \(21\)
    job \(4\): \(M_2\to M_1\) \((25,8,14)\) \(25\)
    job \(4\): \(M_2\to M_3\) \((18,8,21)\) \(21\)
    job \(5\): \(M_1\to M_2\) \((13,20,14)\) \(20\)
    job \(5\): \(M_1\to M_3\) \((13,15,19)\) \(19\)
    job \(6\): \(M_1\to M_2\) \((9,24,14)\) \(24\)
    job \(6\): \(M_1\to M_3\) \((9,15,23)\) \(23\)
    job \(7\): \(M_3\to M_1\) \((26,15,6)\) \(26\)
    job \(7\): \(M_3\to M_2\) \((18,23,6)\) \(23\)

    No move is improving: local optimum.

    The schedule of \(LPT\) is a local optimum for move, with \(C_{\max}=18\).

  3. Iteration 1: \(J_{1}=\{2,5,6\}, J_{2}=\{1,4\}, J_{3}=\{3,7\}\), loads \((18,15,14)\), \(C_{\max}=18\).

    swap loads \(C_{\max}\)
    jobs \(1,2\) (\(M_2,M_1\)) \((22,11,14)\) \(22\)
    jobs \(1,3\) (\(M_2,M_3\)) \((18,13,16)\) \(18\)
    jobs \(1,5\) (\(M_2,M_1\)) \((21,12,14)\) \(21\)
    jobs \(1,6\) (\(M_2,M_1\)) \((17,16,14)\) \(17\) \(\leftarrow\)
    jobs \(2,3\) (\(M_1,M_3\)) \((20,15,12)\) \(20\)
    jobs \(2,4\) (\(M_1,M_2\)) \((21,12,14)\) \(21\)
    jobs \(2,7\) (\(M_1,M_3\)) \((22,15,10)\) \(22\)
    jobs \(3,4\) (\(M_3,M_2\)) \((18,14,15)\) \(18\)
    jobs \(3,5\) (\(M_3,M_1\)) \((19,15,13)\) \(19\)
    jobs \(3,6\) (\(M_3,M_1\)) \((15,15,17)\) \(17\)
    jobs \(4,5\) (\(M_2,M_1\)) \((20,13,14)\) \(20\)
    jobs \(4,6\) (\(M_2,M_1\)) \((16,17,14)\) \(17\)
    jobs \(4,7\) (\(M_2,M_3\)) \((18,16,13)\) \(18\)
    jobs \(5,7\) (\(M_1,M_3\)) \((21,15,11)\) \(21\)
    jobs \(6,7\) (\(M_1,M_3\)) \((17,15,15)\) \(17\)

    The swap marked is accepted.

    Iteration 2: \(J_{1}=\{1,2,5\}, J_{2}=\{4,6\}, J_{3}=\{3,7\}\), loads \((17,16,14)\), \(C_{\max}=17\).

    swap loads \(C_{\max}\)
    jobs \(1,3\) (\(M_1,M_3\)) \((15,16,16)\) \(16\) \(\leftarrow\)
    jobs \(1,4\) (\(M_1,M_2\)) \((16,17,14)\) \(17\)
    jobs \(1,6\) (\(M_1,M_2\)) \((18,15,14)\) \(18\)
    jobs \(2,3\) (\(M_1,M_3\)) \((19,16,12)\) \(19\)
    jobs \(2,4\) (\(M_1,M_2\)) \((20,13,14)\) \(20\)
    jobs \(2,6\) (\(M_1,M_2\)) \((22,11,14)\) \(22\)
    jobs \(2,7\) (\(M_1,M_3\)) \((21,16,10)\) \(21\)
    jobs \(3,4\) (\(M_3,M_2\)) \((17,15,15)\) \(17\)
    jobs \(3,5\) (\(M_3,M_1\)) \((18,16,13)\) \(18\)
    jobs \(3,6\) (\(M_3,M_2\)) \((17,13,17)\) \(17\)
    jobs \(4,5\) (\(M_2,M_1\)) \((19,14,14)\) \(19\)
    jobs \(4,7\) (\(M_2,M_3\)) \((17,17,13)\) \(17\)
    jobs \(5,6\) (\(M_1,M_2\)) \((21,12,14)\) \(21\)
    jobs \(5,7\) (\(M_1,M_3\)) \((20,16,11)\) \(20\)
    jobs \(6,7\) (\(M_2,M_3\)) \((17,15,15)\) \(17\)

    The swap marked is accepted.

    Iteration 3: \(J_{1}=\{2,3,5\}, J_{2}=\{4,6\}, J_{3}=\{1,7\}\), loads \((15,16,16)\), \(C_{\max}=16\).

    swap loads \(C_{\max}\)
    jobs \(1,2\) (\(M_3,M_1\)) \((19,16,12)\) \(19\)
    jobs \(1,3\) (\(M_3,M_1\)) \((17,16,14)\) \(17\)
    jobs \(1,4\) (\(M_3,M_2\)) \((15,17,15)\) \(17\)
    jobs \(1,5\) (\(M_3,M_1\)) \((18,16,13)\) \(18\)
    jobs \(1,6\) (\(M_3,M_2\)) \((15,15,17)\) \(17\)
    jobs \(2,4\) (\(M_1,M_2\)) \((18,13,16)\) \(18\)
    jobs \(2,6\) (\(M_1,M_2\)) \((20,11,16)\) \(20\)
    jobs \(2,7\) (\(M_1,M_3\)) \((19,16,12)\) \(19\)
    jobs \(3,4\) (\(M_1,M_2\)) \((16,15,16)\) \(16\)
    jobs \(3,6\) (\(M_1,M_2\)) \((18,13,16)\) \(18\)
    jobs \(3,7\) (\(M_1,M_3\)) \((17,16,14)\) \(17\)
    jobs \(4,5\) (\(M_2,M_1\)) \((17,14,16)\) \(17\)
    jobs \(4,7\) (\(M_2,M_3\)) \((15,17,15)\) \(17\)
    jobs \(5,6\) (\(M_1,M_2\)) \((19,12,16)\) \(19\)
    jobs \(5,7\) (\(M_1,M_3\)) \((18,16,13)\) \(18\)
    jobs \(6,7\) (\(M_2,M_3\)) \((15,15,17)\) \(17\)

    No swap is improving: local optimum.

    The swap local search makes 2 moves, \(18\to17\to16\), and stops in \(J_{1}=\{2,3,5\}, J_{2}=\{4,6\}, J_{3}=\{1,7\}\).

  4. The bound is \(\lceil 47/3\rceil=16\), attained by the final schedule: it is optimal. The schedule of \(LPT\) is a local optimum for move and not for swap: the local optimum depends on the neighbourhood.

Exercise 31.12: Local search \(P\,||\,C_{\max}\) 3

\(m=3\) identical machines and \(6\) jobs with processing times

\[ \begin{array}{l|cccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\[1ex] \hline {t_j} & {5} & {5} & {7} & {9} & {2} & {7} \\ \hline \end{array} \]

A move reassigns one job \(j\) to another machine \(h\) (examined for \(j=1,\dots,n\) and \(h=1,\dots,m\)); a swap exchanges the machines of two jobs \(j<k\) on different machines with \(t_j\ne t_k\). The local searches use the best-improvement rule, with ties broken in favour of the move examined first.

Questions

  1. Compute the schedule of list scheduling (\(LIST\)) with the jobs in the order \(1,2,\dots,n\), and its makespan. How many machines are critical?

  2. Apply the move local search with the makespan as objective, starting from the schedule of \(LIST\). Why does it stop?

  3. Apply the move local search with the auxiliary objective \(\sum_h L_h^2\) (minimized), starting from the schedule of \(LIST\).

  4. Compute the lower bound \(\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}\) and conclude.

Solution

    • job \(1\) (\(t_{1}=5\)) goes to machine \(1\), the least loaded (load \(0\)), which reaches \(5\);

    • job \(2\) (\(t_{2}=5\)) goes to machine \(2\), the least loaded (load \(0\)), which reaches \(5\);

    • job \(3\) (\(t_{3}=7\)) goes to machine \(3\), the least loaded (load \(0\)), which reaches \(7\);

    • job \(4\) (\(t_{4}=9\)) goes to machine \(1\), the least loaded (load \(5\)), which reaches \(14\);

    • job \(5\) (\(t_{5}=2\)) goes to machine \(2\), the least loaded (load \(5\)), which reaches \(7\);

    • job \(6\) (\(t_{6}=7\)) goes to machine \(2\), the least loaded (load \(7\)), which reaches \(14\);

    The schedule is \(J_{1}=\{1,4\}, J_{2}=\{2,5,6\}, J_{3}=\{3\}\), with loads \((14,14,7)\) and \(C_{\max}=14\): 2 machines are critical.

  2. Iteration 1: \(J_{1}=\{1,4\}, J_{2}=\{2,5,6\}, J_{3}=\{3\}\), loads \((14,14,7)\), \(C_{\max}=14\).

    move loads \(C_{\max}\)
    job \(1\): \(M_1\to M_2\) \((9,19,7)\) \(19\)
    job \(1\): \(M_1\to M_3\) \((9,14,12)\) \(14\)
    job \(2\): \(M_2\to M_1\) \((19,9,7)\) \(19\)
    job \(2\): \(M_2\to M_3\) \((14,9,12)\) \(14\)
    job \(3\): \(M_3\to M_1\) \((21,14,0)\) \(21\)
    job \(3\): \(M_3\to M_2\) \((14,21,0)\) \(21\)
    job \(4\): \(M_1\to M_2\) \((5,23,7)\) \(23\)
    job \(4\): \(M_1\to M_3\) \((5,14,16)\) \(16\)
    job \(5\): \(M_2\to M_1\) \((16,12,7)\) \(16\)
    job \(5\): \(M_2\to M_3\) \((14,12,9)\) \(14\)
    job \(6\): \(M_2\to M_1\) \((21,7,7)\) \(21\)
    job \(6\): \(M_2\to M_3\) \((14,7,14)\) \(14\)

    No move is improving: local optimum.

    Two machines have load \(14\). A move changes only two loads, and lowers the makespan only if it starts from the unique critical machine: here no move can decrease both critical loads, so the schedule of \(LIST\) is a local optimum. Several moves keep \(C_{\max}=14\): the search is on a plateau.

  3. Iteration 1: \(J_{1}=\{1,4\}, J_{2}=\{2,5,6\}, J_{3}=\{3\}\), loads \((14,14,7)\), \(C_{\max}=14\), \(\sum_hL_h^2=441\).

    move loads \(C_{\max}\) \(\sum_hL_h^2\)
    job \(1\): \(M_1\to M_2\) \((9,19,7)\) \(19\) \(491\)
    job \(1\): \(M_1\to M_3\) \((9,14,12)\) \(14\) \(421\) \(\leftarrow\)
    job \(2\): \(M_2\to M_1\) \((19,9,7)\) \(19\) \(491\)
    job \(2\): \(M_2\to M_3\) \((14,9,12)\) \(14\) \(421\)
    job \(3\): \(M_3\to M_1\) \((21,14,0)\) \(21\) \(637\)
    job \(3\): \(M_3\to M_2\) \((14,21,0)\) \(21\) \(637\)
    job \(4\): \(M_1\to M_2\) \((5,23,7)\) \(23\) \(603\)
    job \(4\): \(M_1\to M_3\) \((5,14,16)\) \(16\) \(477\)
    job \(5\): \(M_2\to M_1\) \((16,12,7)\) \(16\) \(449\)
    job \(5\): \(M_2\to M_3\) \((14,12,9)\) \(14\) \(421\)
    job \(6\): \(M_2\to M_1\) \((21,7,7)\) \(21\) \(539\)
    job \(6\): \(M_2\to M_3\) \((14,7,14)\) \(14\) \(441\)

    The move marked is accepted.

    Iteration 2: \(J_{1}=\{4\}, J_{2}=\{2,5,6\}, J_{3}=\{1,3\}\), loads \((9,14,12)\), \(C_{\max}=14\), \(\sum_hL_h^2=421\).

    move loads \(C_{\max}\) \(\sum_hL_h^2\)
    job \(1\): \(M_3\to M_1\) \((14,14,7)\) \(14\) \(441\)
    job \(1\): \(M_3\to M_2\) \((9,19,7)\) \(19\) \(491\)
    job \(2\): \(M_2\to M_1\) \((14,9,12)\) \(14\) \(421\)
    job \(2\): \(M_2\to M_3\) \((9,9,17)\) \(17\) \(451\)
    job \(3\): \(M_3\to M_1\) \((16,14,5)\) \(16\) \(477\)
    job \(3\): \(M_3\to M_2\) \((9,21,5)\) \(21\) \(547\)
    job \(4\): \(M_1\to M_2\) \((0,23,12)\) \(23\) \(673\)
    job \(4\): \(M_1\to M_3\) \((0,14,21)\) \(21\) \(637\)
    job \(5\): \(M_2\to M_1\) \((11,12,12)\) \(12\) \(409\) \(\leftarrow\)
    job \(5\): \(M_2\to M_3\) \((9,12,14)\) \(14\) \(421\)
    job \(6\): \(M_2\to M_1\) \((16,7,12)\) \(16\) \(449\)
    job \(6\): \(M_2\to M_3\) \((9,7,19)\) \(19\) \(491\)

    The move marked is accepted.

    Iteration 3: \(J_{1}=\{4,5\}, J_{2}=\{2,6\}, J_{3}=\{1,3\}\), loads \((11,12,12)\), \(C_{\max}=12\), \(\sum_hL_h^2=409\).

    move loads \(C_{\max}\) \(\sum_hL_h^2\)
    job \(1\): \(M_3\to M_1\) \((16,12,7)\) \(16\) \(449\)
    job \(1\): \(M_3\to M_2\) \((11,17,7)\) \(17\) \(459\)
    job \(2\): \(M_2\to M_1\) \((16,7,12)\) \(16\) \(449\)
    job \(2\): \(M_2\to M_3\) \((11,7,17)\) \(17\) \(459\)
    job \(3\): \(M_3\to M_1\) \((18,12,5)\) \(18\) \(493\)
    job \(3\): \(M_3\to M_2\) \((11,19,5)\) \(19\) \(507\)
    job \(4\): \(M_1\to M_2\) \((2,21,12)\) \(21\) \(589\)
    job \(4\): \(M_1\to M_3\) \((2,12,21)\) \(21\) \(589\)
    job \(5\): \(M_1\to M_2\) \((9,14,12)\) \(14\) \(421\)
    job \(5\): \(M_1\to M_3\) \((9,12,14)\) \(14\) \(421\)
    job \(6\): \(M_2\to M_1\) \((18,5,12)\) \(18\) \(493\)
    job \(6\): \(M_2\to M_3\) \((11,5,19)\) \(19\) \(507\)

    No move is improving: local optimum.

    The search makes 2 moves, with makespan \(14\to14\to12\) and \(\sum_hL_h^2\): \(441\to421\to409\). The first move does not change the makespan, but it prepares the second one.

  4. The bound is \(\max\{9,\lceil 35/3\rceil\}=12\), attained by the final schedule: it is optimal. The auxiliary objective gives a slope to the plateau of the makespan.