Exercises — Solving ILPs
Chapter 6 · Fully solved exercises on Branch & Bound and Cutting Planes
Exercise 1: Branch & Bound on a 2-Variable ILP
Problem. Solve by Branch & Bound:
\[\max\; 5x_1 + 4x_2\]
\[\text{s.t.}\quad x_1 + x_2 \le 5,\quad 10x_1 + 6x_2 \le 45,\quad x_1,x_2 \ge 0,\quad x_1,x_2 \in \mathbb{Z}.\]
Solution
Root node — LP relaxation.
The LP feasible region has vertices at \((0,0)\), \((4.5,\,0)\), \((3.75,\,1.25)\), and \((0,\,5)\).
The vertex \((3.75,\,1.25)\) is found by solving \(x_1+x_2=5\) and \(10x_1+6x_2=45\) simultaneously: substituting \(x_2=5-x_1\) gives \(10x_1+6(5-x_1)=45 \Rightarrow 4x_1=15 \Rightarrow x_1=3.75\), \(x_2=1.25\).
Objective values at vertices:
| Vertex | \(5x_1+4x_2\) |
|---|---|
| \((0,0)\) | 0 |
| \((4.5,0)\) | 22.5 |
| \((3.75,1.25)\) | 23.75 |
| \((0,5)\) | 20 |
LP optimum: \(x_1^*=3.75\), \(x_2^*=1.25\), \(z_{\text{LP}}=23.75\). Both variables are fractional — branch on \(x_1\).
Node L — add \(x_1 \le 3\).
With \(x_1=3\): from \(10(3)+6x_2\le 45 \Rightarrow x_2\le 2.5\) and \(3+x_2\le 5 \Rightarrow x_2\le 2\). Active upper bound is \(x_2\le 2\), so LP optimum is \(x_1=3\), \(x_2=2\).
\[z_L = 5(3)+4(2) = 23.\]
Both variables are integer. Record incumbent \(z^*=23\), \((x_1,x_2)=(3,2)\).
Node R — add \(x_1 \ge 4\).
With \(x_1=4\): \(10(4)+6x_2\le 45 \Rightarrow x_2\le 5/6\approx 0.833\) and \(4+x_2\le 5 \Rightarrow x_2\le 1\). Active bound is \(x_2\le 5/6\), LP optimum: \(x_1=4\), \(x_2=5/6\).
\[z_R = 5(4)+4(5/6) = 20+10/3 \approx 23.33.\]
\(z_R > z^*=23\), so do not prune — branch on \(x_2\).
Node RL — add \(x_1\ge 4\), \(x_2\le 0\), i.e. \(x_2=0\).
\(x_2=0\), \(10x_1\le 45\Rightarrow x_1\le 4.5\) and \(x_1\le 5\), combined with \(x_1\ge 4\). LP optimum: \(x_1=4.5\), \(x_2=0\), \(z=22.5\). Since \(x_1=4.5\) is fractional, we would branch; but \(\lfloor 22.5\rfloor = 22 < z^*=23\) — prune by bound.
Node RR — add \(x_1\ge 4\), \(x_2\ge 1\).
Check feasibility: \(10(4)+6(1)=46>45\) with \(x_1=4\), \(x_2=1\) already violates the second constraint. Any solution with \(x_1\ge 4\) and \(x_2\ge 1\) has \(10x_1+6x_2\ge 46>45\) — prune by infeasibility.
All nodes explored. Optimal ILP solution:
\[\boxed{x_1=3,\quad x_2=2,\quad z^*=23.}\]
Exercise 2: Pruning Rules
Problem. In a B&B tree for a maximisation ILP, the best integer solution found so far has value \(z^*=18\). For each node state whether to prune and why:
| Node | LP Bound | LP Solution | |
|---|---|---|---|
| (a) | A | 17.5 | fractional |
| (b) | B | 20.3 | \((2.5,\;3.0)\) — \(x_1\) fractional |
| (c) | C | — | LP infeasible |
| (d) | D | 19.0 | \((3,\;4)\) — all integer |
| (e) | E | 18.0 | fractional |
Solution
(a) Node A — LP bound \(17.5 < z^*=18\). Prune by bound: even the LP relaxation cannot beat the current best. All descendants inherit a bound \(\le 17.5\), so no improvement is possible.
(b) Node B — LP bound \(20.3 > 18\), \(x_1\) fractional. Do NOT prune. The bound is promising. Branch on \(x_1\) (the fractional variable).
(c) Node C — LP infeasible. Prune by infeasibility: every feasible integer solution must satisfy the LP relaxation, so if the LP is infeasible then no integer solution lies in this sub-problem either.
(d) Node D — LP bound \(19.0\), solution \((3,4)\) all integer. Do NOT prune — update the incumbent. \((3,4)\) is a feasible integer solution with value \(19 > 18\). Set \(z^*=19\).
(e) Node E — LP bound \(18.0 = z^*\). Prune by bound (weak): since all objective coefficients are integer and all variables must be integer, the ILP value of any solution in this sub-tree is at most \(\lfloor 18.0\rfloor = 18\), which does not improve the current best. Prune.
Exercise 3: Gomory Cut from Tableau
Problem. The LP optimal tableau for \(\max\; 5x_1+4x_2\) subject to \(6x_1+x_2\le 14\) and \(x_1+4x_2\le 12\) is:
| \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS | |
|---|---|---|---|---|---|
| \(x_1\) | 1 | 0 | \(2/5\) | \(-1/5\) | \(16/5\) |
| \(x_2\) | 0 | 1 | \(-1/10\) | \(3/10\) | \(2\) |
| \(z\) | 0 | 0 | \(-9/5\) | \(-1/5\) | \(24\) |
- Is the LP solution integer? (b) Generate a Gomory cut from row 1.
Solution
(a) \(x_1=16/5=3.2\) (fractional), \(x_2=2\) (integer). The LP solution is not fully integer — we need a cut.
(b) Gomory cut from row 1.
Row 1 in the LP tableau is:
\[x_1 + \tfrac{2}{5}s_1 - \tfrac{1}{5}s_2 = \tfrac{16}{5}.\]
Step 1 — fractional part of the RHS. \[f_0 = \text{frac}\!\left(\tfrac{16}{5}\right) = \tfrac{16}{5} - \left\lfloor\tfrac{16}{5}\right\rfloor = \tfrac{16}{5} - 3 = \tfrac{1}{5}.\]
Step 2 — fractional parts of non-basic coefficients.
For \(s_1\): \(\bar{a}_{s_1} = 2/5 \ge 0\), so \(f_{s_1} = \text{frac}(2/5) = 2/5\).
For \(s_2\): \(\bar{a}_{s_2} = -1/5 < 0\), so \(f_{s_2} = \text{frac}(-1/5) = -1/5 - \lfloor-1/5\rfloor = -1/5 - (-1) = 4/5\).
Step 3 — write the Gomory inequality.
\[\sum_j f_j \cdot s_j \ge f_0 \quad\Longrightarrow\quad \tfrac{2}{5}s_1 + \tfrac{4}{5}s_2 \ge \tfrac{1}{5}.\]
Multiply by 5: \[2s_1 + 4s_2 \ge 1.\]
Step 4 — back-substitute \(s_1=14-6x_1-x_2\) and \(s_2=12-x_1-4x_2\):
\[2(14-6x_1-x_2)+4(12-x_1-4x_2) \ge 1\] \[28-12x_1-2x_2+48-4x_1-16x_2 \ge 1\] \[76-16x_1-18x_2 \ge 1\]
\[\boxed{16x_1+18x_2 \le 75.}\]
This new constraint cuts off the fractional LP point \((3.2,\,2)\) while remaining valid for all integer-feasible points (verified below in Exercise 4).
Exercise 4: Why is Cutting Planes Correct?
Problem. Show that the Gomory cut \(16x_1+18x_2\le 75\) is valid — i.e. satisfied by every integer-feasible point of the original problem — and that it cuts off the LP optimum \((3.2,\,2)\).
Solution
The original ILP feasible region (constraints \(6x_1+x_2\le 14\), \(x_1+4x_2\le 12\), \(x_1,x_2\ge 0\), \(x_1,x_2\in\mathbb{Z}\)) has the following integer points:
| \((x_1,x_2)\) | \(6x_1+x_2\) | \(x_1+4x_2\) | \(16x_1+18x_2\) | \(\le 75\)? |
|---|---|---|---|---|
| \((0,0)\) | 0 | 0 | 0 | ✓ |
| \((0,1)\) | 1 | 4 | 18 | ✓ |
| \((0,2)\) | 2 | 8 | 36 | ✓ |
| \((0,3)\) | 3 | 12 | 54 | ✓ |
| \((1,0)\) | 6 | 1 | 16 | ✓ |
| \((1,1)\) | 7 | 5 | 34 | ✓ |
| \((1,2)\) | 8 | 9 | 52 | ✓ |
| \((2,0)\) | 12 | 2 | 32 | ✓ |
| \((2,1)\) | 13 | 6 | 50 | ✓ |
| \((2,2)\) | 14 | 10 | 68 | ✓ |
The point \((2,2)\) is the last feasible point as \(x_1\) increases (at \(x_1=3\): \(6(3)=18>14\), infeasible). All integer-feasible points satisfy \(16x_1+18x_2\le 75\).
The LP optimum \((3.2,\,2)\) violates the cut: \[16(3.2)+18(2)=51.2+36=87.2 > 75. \quad\checkmark\]
Why does the Gomory procedure guarantee validity? The cut \(2s_1+4s_2\ge 1\) was derived from row 1 of the LP tableau by taking fractional parts of the coefficients. For any integer solution, \(s_1=14-6x_1-x_2\) and \(s_2=12-x_1-4x_2\) are also non-negative integers (since the original constraints are integer-coefficient, integer-RHS inequalities). Two non-negative integers satisfying \(2s_1+4s_2\ge 1\) must in fact satisfy \(2s_1+4s_2\ge 2\) (the LHS is always even), which is consistent with — and equivalent to — \(16x_1+18x_2\le 75\) in the original space. Hence no integer-feasible point is cut off.
ILP optimal solution: \((x_1,x_2)=(2,2)\), \(z^*=5(2)+4(2)=18\).
Exercise 5: B&B vs Cutting Planes
Problem. Compare Branch & Bound and Cutting Planes on the ILP of Exercise 1. Which converges faster here? Describe the trade-offs.
Solution
B&B on Exercise 1 — recap.
| Node | Description | Outcome |
|---|---|---|
| Root | LP opt \((3.75,1.25)\), \(z=23.75\) | Branch on \(x_1\) |
| Node L \((x_1\le 3)\) | Integer opt \((3,2)\), \(z=23\) | Incumbent \(z^*=23\) |
| Node R \((x_1\ge 4)\) | LP opt \((4,\,5/6)\), \(z\approx 23.33\) | Branch on \(x_2\) |
| Node RL \((x_2\le 0)\) | LP opt \((4.5,0)\), \(z=22.5<23\) | Prune (bound) |
| Node RR \((x_2\ge 1)\) | Infeasible | Prune (infeasibility) |
Total: 5 nodes explored (root + 4 children).
Cutting Planes on Exercise 1 — analysis.
The LP optimum is \((3.75,1.25)\), \(z=23.75\). A Gomory cut from the \(x_1\)-row of the tableau would add a constraint cutting off \((3.75,1.25)\). After one Gomory cut the new LP optimum moves to, e.g., \(x_1=3\), \(x_2=2\) (since the cut tightens the feasible region toward the integer hull). If the LP after the first cut gives an integer solution directly, only 1 LP solve + 1 re-solve is needed — fewer than B&B’s 5 nodes. However, in general, multiple cuts may be required, and each LP re-solve can be more expensive than a single B&B node.
Comparison.
| Criterion | Branch & Bound | Cutting Planes |
|---|---|---|
| This example | 5 nodes | 1–2 LP re-solves (lucky case) |
| Large, dense ILPs | Can branch exponentially | Polynomial number of cuts (in theory) |
| Sparse / structured ILPs | Exploits problem structure well | Cuts may be weak / slow to tighten |
| Memory usage | Tree can be large | Only one LP maintained |
| Practical use | Dominant in MIP solvers | Used as preprocessing (cut rounds) |
Modern solvers (CPLEX, Gurobi, SCIP) use Branch-and-Cut: B&B with cutting planes added at each node to tighten LP bounds before branching.