Exercises — Integer Linear Programming
Chapter 3 · Fully solved exercises on ILP models, LP relaxation, and integrality gap
Exercise 1: Knapsack LP Relaxation Bound
Problem. Consider a 0/1 knapsack problem with capacity \(W = 10\) and the following items:
| Item | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Weight | 4 | 3 | 5 | 2 |
| Value | 7 | 5 | 9 | 3 |
Find: (a) the LP relaxation optimum \(z^*_{\text{LP}}\), (b) a good integer feasible solution, (c) tight bounds on \(z^*_{\text{ILP}}\).
Solution
(a) LP relaxation — greedy by value-to-weight ratio.
| Item | Weight | Value | Ratio |
|---|---|---|---|
| 3 | 5 | 9 | 1.80 |
| 1 | 4 | 7 | 1.75 |
| 2 | 3 | 5 | 1.67 |
| 4 | 2 | 3 | 1.50 |
Fill greedily in decreasing ratio order:
- Take item 3 fully: \(w = 5\), \(v = 9\), remaining capacity \(= 5\).
- Take item 1 fully: \(w = 4\), \(v = 7\), remaining capacity \(= 1\).
- Take \(\tfrac{1}{3}\) of item 2: fractional \(x_2 = 1/3\), value \(= 5/3\).
\[z^*_{\text{LP}} = 9 + 7 + \frac{5}{3} = 16 + \frac{5}{3} = \frac{53}{3} \approx 17.67\]
(b) Integer feasible solutions.
| Selection | Weight | Value |
|---|---|---|
| \(\{3,1\}\) | 9 | 16 |
| \(\{3,2\}\) | 8 | 14 |
| \(\{1,2,4\}\) | 9 | 15 |
| \(\{2,3,4\}\) | 10 | 17 |
The best integer solution found so far is \(\{2,3,4\}\) with value 17 and weight exactly 10.
(c) Bounds on \(z^*_{\text{ILP}}\).
Since \(z^*_{\text{LP}} = 53/3 \approx 17.67\), the ILP optimum satisfies \(z^*_{\text{ILP}} \leq \lfloor 17.67 \rfloor = 17\). Since we have an integer feasible solution with value 17, we get \(z^*_{\text{ILP}} \geq 17\).
Therefore \(z^*_{\text{ILP}} = \mathbf{17}\), achieved by items \(\{2, 3, 4\}\).
Exercise 2: Integrality Gap
Problem. Using the instance from Exercise 1, compute the integrality gap. Is the LP relaxation a good approximation?
Solution
The integrality gap for a maximisation problem is defined as:
\[\text{gap} = \frac{z^*_{\text{LP}}}{z^*_{\text{ILP}}}\]
\[\text{gap} = \frac{53/3}{17} = \frac{53}{51} \approx 1.039\]
The gap is approximately 3.9%, meaning the LP relaxation overestimates the true optimum by less than 4%. This is a small gap, so the LP relaxation is a good approximation for this instance.
Exercise 3: Vertex Cover ILP
Problem. Given a graph \(G = (V, E)\) with \(V = \{1,2,3,4,5\}\) and edges \(E = \{1\text{-}2,\ 1\text{-}3,\ 2\text{-}4,\ 3\text{-}4,\ 4\text{-}5\}\), formulate a minimum vertex cover ILP and find the optimal cover.
Solution
ILP formulation. Introduce a binary variable \(x_v \in \{0,1\}\) for each node \(v\), equal to 1 if \(v\) is in the cover.
\[ \begin{aligned} & \text{minimize} && \sum_{v \in V} x_v \\ & \text{subject to} && x_u + x_v \geq 1 && \forall\, \{u,v\} \in E \\ & && x_v \in \{0,1\} && \forall\, v \in V \end{aligned} \]
Constraints written out:
| Edge | Constraint |
|---|---|
| 1-2 | \(x_1 + x_2 \geq 1\) |
| 1-3 | \(x_1 + x_3 \geq 1\) |
| 2-4 | \(x_2 + x_4 \geq 1\) |
| 3-4 | \(x_3 + x_4 \geq 1\) |
| 4-5 | \(x_4 + x_5 \geq 1\) |
Finding the optimal cover.
- Node 4 is incident to edges 2-4, 3-4, 4-5 — set \(x_4 = 1\). Remaining uncovered: \(\{1\text{-}2,\ 1\text{-}3\}\).
- Node 1 is incident to both 1-2 and 1-3 — set \(x_1 = 1\). All edges covered.
- Cover \(\{1,4\}\), size 2.
Verification:
| Edge | Covered by |
|---|---|
| 1-2 | \(x_1 = 1\) |
| 1-3 | \(x_1 = 1\) |
| 2-4 | \(x_4 = 1\) |
| 3-4 | \(x_4 = 1\) |
| 4-5 | \(x_4 = 1\) |
Can we achieve size 1? Node 4 alone misses 1-2 and 1-3; node 1 alone misses 2-4, 3-4, 4-5. No single node covers all edges. Therefore \(z^*_{\text{ILP}} = \mathbf{2}\), achieved by \(\{1, 4\}\).
Exercise 4: LP Relaxation Geometry
Problem. Consider the ILP:
\[ \begin{aligned} & \text{maximize} && x_1 + x_2 \\ & \text{subject to} && x_1 + 2x_2 \leq 7 \\ & && 2x_1 + x_2 \leq 7 \\ & && x_1, x_2 \in \{0,1,2,3\} \end{aligned} \]
- Find the LP relaxation optimum (dropping the integrality constraint, keeping \(x_1,x_2\geq 0\)).
- Find the ILP optimum.
- Compute the integrality gap.
Solution
(a) LP relaxation.
The LP feasible region is a polygon. Key vertices:
| Vertex | \(x_1\) | \(x_2\) | \(x_1+x_2\) |
|---|---|---|---|
| \((0,0)\) | 0 | 0 | 0 |
| \((7/2,0)\) | 3.5 | 0 | 3.5 |
| \((7/3,7/3)\) | 2.33 | 2.33 | 4.67 |
| \((0,7/2)\) | 0 | 3.5 | 3.5 |
The objective \(x_1+x_2\) is maximised at the symmetric vertex \((7/3, 7/3)\):
\[z^*_{\text{LP}} = \frac{7}{3} + \frac{7}{3} = \frac{14}{3} \approx 4.67\]
(b) ILP optimum.
We search integer points \(x_1, x_2 \in \{0,1,2,3\}\) satisfying both constraints:
| \((x_1, x_2)\) | \(x_1+2x_2\) | \(2x_1+x_2\) | Feasible? | \(z\) |
|---|---|---|---|---|
| \((3,1)\) | 5 | 7 | Yes | 4 |
| \((2,2)\) | 6 | 6 | Yes | 4 |
| \((1,3)\) | 7 | 5 | Yes | 4 |
| \((3,2)\) | 7 | 8 | No | — |
Multiple optimal solutions with \(z^*_{\text{ILP}} = \mathbf{4}\).
(c) Integrality gap.
\[\text{gap} = \frac{z^*_{\text{LP}}}{z^*_{\text{ILP}}} = \frac{14/3}{4} = \frac{14}{12} = \frac{7}{6} \approx 1.167\]
Gap \(\approx 16.7\%\) — moderate. The LP overestimates the integer optimum by about \(0.67\) units.
Exercise 5: True/False — ILP Concepts
Problem. Answer True or False with justification:
- Every feasible ILP has an optimal integer solution that is also optimal for its LP relaxation.
- If the LP relaxation is infeasible, the ILP is also infeasible.
- For a maximisation ILP, \(z^*_{\text{LP}} \geq z^*_{\text{ILP}}\) always holds.
- If all variables at the LP relaxation optimum are integer, then this LP solution is also ILP optimal.
Solution
(a) FALSE.
The LP optimal is generally a fractional point. The ILP optimal is a different (integer) point, typically with a strictly lower objective value for maximisation. They coincide only in special cases.
(b) TRUE.
The ILP feasible set \(\mathcal{F}_{\text{ILP}} \subseteq \mathcal{F}_{\text{LP}}\) (every integer feasible point satisfies the LP constraints). If \(\mathcal{F}_{\text{LP}} = \emptyset\), then \(\mathcal{F}_{\text{ILP}} = \emptyset\) as well.
(c) TRUE.
The LP relaxation maximises over the set \(\mathcal{F}_{\text{LP}} \supseteq \mathcal{F}_{\text{ILP}}\). Optimising over a larger set cannot yield a smaller maximum:
\[z^*_{\text{LP}} = \max_{x \in \mathcal{F}_{\text{LP}}} c^T x \;\geq\; \max_{x \in \mathcal{F}_{\text{ILP}}} c^T x = z^*_{\text{ILP}}\]
(d) TRUE.
If the LP optimal solution \(x^*\) is integer, then \(x^* \in \mathcal{F}_{\text{ILP}}\) and \(c^T x^* = z^*_{\text{LP}} \geq z^*_{\text{ILP}}\). Since \(z^*_{\text{ILP}} \leq c^T x^* \leq z^*_{\text{ILP}}\), equality holds and \(x^*\) is ILP optimal.