31.10 KP: feasibility and penalties¶
Part 4 · Heuristic algorithms · Chapter 31 · Chapter 31: Local search · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Local search · App: TSP: nearest neighbour and 2-opt
-
The representation of the KP by a binary vector \(x\) describes also infeasible objects, whose weight exceeds the capacity. There are two ways of dealing with them:
-
stay feasible: the neighbourhood contains only the feasible neighbours, as done so far;
-
penalize: the infeasible vectors are allowed, and the search maximizes a function that subtracts from the profit a penalty proportional to the excess weight.
-
-
Staying feasible can make the search short-sighted. In the chapter «Heuristic algorithms: definitions», \(x=(1,0,1,0)\) is a local optimum for flip: to reach the optimal solution \((1,1,0,0)\) with flips one has to add item \(2\) and remove item \(3\), and the intermediate vector is either \((1,1,1,0)\), infeasible, or \((1,0,0,0)\), of profit \(10<16\). The swap neighbourhood solves this case by performing the two flips at once; penalties solve it by letting the search walk through the infeasible vector.
-
With penalties, the search space is the whole set \(\{0,1\}^n\), and the function to maximize is
where \(\alpha>0\) is the penalty for each unit of excess weight. For a feasible \(x\), \(g_\alpha(x)\) is the profit of \(x\).
31.10.1 Staying feasible¶
The flip+swap local search for the KP examines the flips and then the swaps of the current solution, discards those that exceed the capacity, applies an improving one chosen by the first- or the best-improvement rule, and stops when no feasible neighbour has a larger profit.
Algorithm: Flip+swap step for the KP
- With the first-improvement rule, if an improving flip is found the swaps are not examined. Only flips that add an item can improve the profit; flips that remove an item are kept in the neighbourhood for uniformity. An iteration costs \(O(n^2)\) time, because of the swaps.
31.10.2 Penalizing the excess weight¶
The penalty flip local search for the KP examines the flips of the current vector, feasible or not, evaluates them with \(g_\alpha\), applies an improving one chosen by the first- or the best-improvement rule, and stops when no flip increases \(g_\alpha\).
Algorithm: Penalty flip step for the KP
- The local optimum may be infeasible. The search must therefore remember the best feasible solution visited, which is the solution it returns.
Example 31.8: Penalties on the KP reference instance
We start from the solution of \(GR\), \(x=(1,0,1,0)\), of weight \(8\) and profit \(16\), which is a local optimum for the flip neighbourhood restricted to feasible solutions. The values \(g_\alpha\) of its four flips are
| flip | vector | weight | excess | \(\alpha=1\) | \(\alpha=2\) | \(\alpha=\frac94\) | \(\alpha=3\) |
|---|---|---|---|---|---|---|---|
| \(1\) | \((0,0,1,0)\) | \(3\) | \(0\) | \(6\) | \(6\) | \(6\) | \(6\) |
| \(2\) | \((1,1,1,0)\) | \(12\) | \(3\) | \(20\) | \(17\) | \(\frac{65}{4}\) | \(14\) |
| \(3\) | \((1,0,0,0)\) | \(5\) | \(0\) | \(10\) | \(10\) | \(10\) | \(10\) |
| \(4\) | \((1,0,1,1)\) | \(11\) | \(2\) | \(18\) | \(16\) | \(\frac{31}{2}\) | \(14\) |
The two rules make the same moves:
-
\(\alpha=1\): the search adds item \(2\) (\(g_1=20\)), then item \(4\) (\(g_1=27-6=21\)), and stops in \((1,1,1,1)\), of weight \(15\): every flip of it removes one item and gives \(16\), \(18\), \(18\) or \(20\). The penalty is too small: the local optimum is infeasible, and the best feasible solution visited is the starting one, of profit \(16\).
-
\(\alpha=2\): the search adds item \(2\) (\(g_2=17>16\)) and stops in \((1,1,1,0)\), infeasible: removing item \(3\) gives \((1,1,0,0)\) with \(g_2=17\), not strictly better.
-
\(\alpha=\frac94\): the search adds item \(2\) (\(g=\frac{65}{4}=16.25>16\)) and then removes item \(3\), reaching \((1,1,0,0)\), of profit \(17\): the optimal solution, through an infeasible vector (see the figure).
-
\(\alpha=3\): no flip improves, and the search stops at once in \((1,0,1,0)\), as the feasible search.
Proposition 31.7
Let the data be integer and let \(\alpha>\max_{j\in\mathscr{I}} p_j\). Then:
-
from a feasible vector, no flip that produces an infeasible vector increases \(g_\alpha\);
-
every infeasible vector has a flip that increases \(g_\alpha\).
Proof
(1) If adding item \(k\) to a feasible vector produces an excess \(e\ge1\), then \(g_\alpha\) changes by \(p_k-\alpha e\le p_k-\alpha<0\). (2) Let \(x\) be infeasible, with excess \(e\ge 1\), and let \(j\) be a selected item. Removing \(j\) decreases the excess by \(\min\{w_j,e\}\ge 1\), so \(g_\alpha\) changes by \(-p_j+\alpha\min\{w_j,e\}\ge -p_j+\alpha>0\). □
- With a large penalty the local optima are feasible, but the search never leaves the feasible region; with a small penalty it crosses the infeasible region, but may stop there. The useful values depend on the instance (here \(\frac94\) works, \(1\), \(2\) and \(3\) do not), so in practice \(\alpha\) is adjusted during the search: increased while the search stays among infeasible vectors, decreased while it stays among feasible ones.