Branch and Bound and Cutting Plane Methods
The previous chapter showed how to write an integer program and why rounding its linear-programming answer will not do. This chapter shows how integer programs are actually solved. Two great ideas do the work. Branch and bound splits the problem into ever-smaller pieces and uses the relaxation bound to throw away pieces that cannot contain the optimum — an intelligent, self-pruning enumeration. Cutting planes take the opposite tack, tightening the relaxation itself by adding inequalities that shave off fractional corners while sparing every integer point. Modern solvers weave the two together into branch-and-cut.
- Why brute-force enumeration is hopeless, and how implicit enumeration avoids it.
- The branch-and-bound framework: bound, branch, and fathom.
- How to branch on a fractional variable into two mutually exclusive subproblems.
- The three fathoming rules — infeasibility, bound, and integrality — and the role of the incumbent.
- A complete worked branch-and-bound tree, plus depth-first vs best-first search.
- Cutting-plane methods (Gomory cuts) and how modern branch-and-cut combines both ideas.
The Challenge of Discreteness
An integer program has only finitely many feasible solutions, so in principle one could list them all and pick the best. In practice this is hopeless: a problem with \(n\) binary variables has up to \(2^{n}\) candidates, and \(2^{50}\) already exceeds a quadrillion. The art is to search this space implicitly — to reason about whole families of solutions at once and discard the unpromising ones without ever examining them individually.
Both methods of this chapter lean on the same lever introduced in Chapter 15: the LP relaxation, whose optimal value bounds the integer optimum. Branch and bound uses that bound to prune; cutting planes strengthen the relaxation until its own optimum happens to be integer. Throughout we use the maximization example carried over from the previous chapter.
Its LP relaxation is optimal at \((3.75,\ 2.25)\) with value \(41.25\); the integer optimum, which we will now derive rather than assert, is \((5, 0)\) with value \(40\).
Bound, Branch, Fathom
Branch and bound organises the search as a tree. Each node is a subproblem — the original integer program plus some extra bounds on the variables. At every node we solve the LP relaxation and then decide, using three rules, whether the node can be closed (fathomed) or must be split (branched). A running best integer solution, the incumbent, records the best value found so far.
Branching
When a node's LP solution has a variable at a fractional value \(x_j = f\), no integer solution can have \(x_j\) strictly between \(\lfloor f \rfloor\) and \(\lceil f \rceil\). We may therefore split the node into two subproblems that together keep every integer point but exclude the fractional one:
The two branches are exhaustive (no integer solution is lost) and mutually exclusive (no overlap), so the tree explores the whole integer space without duplication. In the running example the root LP gives \(x_1 = 3.75\); branching produces \(x_1 \le 3\) and \(x_1 \ge 4\).
The Three Fathoming Rules
A node is fathomed — closed off, needing no further branching — when any one of three conditions holds. For a maximization problem with incumbent value \(\underline{z}\):
(1) Infeasibility: the subproblem has no feasible point, so it holds no solution. (2) Bound: the node's LP value cannot beat the best integer solution already found, so nothing better lies below it. (3) Integrality: the LP solution is already integer — it is a candidate; if it beats the incumbent, update \(\underline{z}\). In every case, no branching is needed. When all nodes are fathomed, the incumbent is optimal.
A Complete Worked Example
We now solve the running example in full. Read the tree top to bottom; each box shows a node's LP result and the rule that closed it.
The root branches on \(x_1\). The \(x_1 \le 3\) child yields an integer point \((3,3)\) worth \(39\), the first incumbent. The \(x_1 \ge 4\) child relaxes to \((4, 1.8)\) worth \(41\) — above \(39\), so it must be explored, and it branches on \(x_2\). The \(x_2 \ge 2\) branch is infeasible; the \(x_2 \le 1\) branch relaxes to \((4.44, 1)\) worth \(40.56\) and branches again on \(x_1\), producing \((4,1)\) worth \(37\) — fathomed by the bound since \(37 < 39\) — and \((5,0)\) worth \(40\), which raises the incumbent. With every node fathomed, \((5,0)\) with \(z = 40\) is optimal.
Search Strategy & Efficiency
Two choices strongly affect how quickly the tree collapses: which node to explore next and which fractional variable to branch on.
| Choice | Common strategies and their trade-offs |
|---|---|
| Node selection | Depth-first dives to integer solutions quickly, giving an early incumbent and using little memory; best-first (best bound) explores the most promising node and tends to prove optimality with fewer nodes but uses more memory. |
| Branching variable | Branch on the most fractional variable (value nearest \(0.5\)), or use pseudo-cost / reliability rules that estimate which split most tightens the bound. |
| Incumbent | A good early incumbent — from rounding heuristics or depth-first diving — sharpens rule (2) and prunes aggressively. |
No strategy escapes the fundamental difficulty: integer programming is NP-hard, so no method is guaranteed to run in polynomial time on every instance. The goal of good strategy is to make the typical problem tractable by keeping the explored tree small.
Cutting-Plane Methods
Cutting-plane methods attack the fractional optimum directly. Solve the LP relaxation; if the answer is integer, you are done. Otherwise add a new linear constraint — a cut — that is satisfied by every integer-feasible point but violated by the current fractional optimum. Re-solve, and repeat. Each cut trims a sliver off the relaxation's feasible region without losing a single integer point, driving the LP optimum toward integrality.
The classic recipe for generating such cuts is Gomory's fractional cut, read off a row of the optimal simplex tableau. If a basic variable is fractional, its row \(x_{B} + \sum_j \bar a_j x_j = \bar b\) with fractional \(\bar b\) yields a valid inequality in the fractional parts \(f_j = \bar a_j - \lfloor \bar a_j \rfloor\) and \(f_0 = \bar b - \lfloor \bar b \rfloor\):
Every integer-feasible solution obeys the inequality (it follows from integrality of the tableau row), so no integer point is lost. Yet at the current vertex all the \(x_j\) are zero (non-basic), making the left side \(0 < f_0\) — the cut is violated, so re-solving must move to a new, less fractional vertex. Adding cuts one at a time is guaranteed to terminate at an integer optimum.
Worked Examples
Problem. A node's LP optimum is \((x_1, x_2, x_3) = (2,\ 3.4,\ 1)\). On which variable do you branch, and into what two subproblems?
Solution. Only \(x_2 = 3.4\) is fractional, so branch on it: the two children add \(x_2 \le 3\) and \(x_2 \ge 4\). Together they keep every integer point and exclude the current fractional one.
Problem. The incumbent value is \(\underline{z} = 39\). A node's LP relaxation gives value \(37.5\). What do you do?
Solution. Fathom by the bound rule: since \(37.5 \le 39\), no integer solution beneath this node can beat the incumbent, so it is closed without branching — even though its LP solution may be fractional.
Problem. In the running example, carry out the root branching and evaluate the \(x_1 \le 3\) child.
Solution. The root LP gives \(x_1 = 3.75\), so branch into \(x_1 \le 3\) and \(x_1 \ge 4\). Solving the \(x_1 \le 3\) subproblem, the LP optimum is the integer point \((3,3)\) with \(z = 39\). By the integrality rule it is fathomed and becomes the first incumbent.
Problem. Why is the branch \(x_1 \ge 4,\ x_2 \ge 2\) infeasible in the running example?
Solution. Together these force \(x_1 + x_2 \ge 6\); with the constraint \(x_1 + x_2 \le 6\) this pins \(x_1 + x_2 = 6\). Substituting \(x_2 = 6 - x_1\) into \(9x_1 + 5x_2 \le 45\) gives \(4x_1 + 30 \le 45\), i.e. \(x_1 \le 3.75\) — contradicting \(x_1 \ge 4\). No feasible point exists, so the node is fathomed.
Problem. The LP \(\max x_2\) subject to \(3x_1 + 2x_2 \le 6,\ 2x_2 \le 3x_1,\ x \ge 0\) has optimum \((1,\ 1.5)\). Find a cut that yields the integer optimum.
Solution. Every integer-feasible point has \(x_2 \le 1\) (since \(x_2 = 1.5\) is impossible for integers here), yet the LP optimum violates it. Adding the cut \(x_2 \le 1\) and re-solving gives \((1, 1)\) with \(z = 1\) — integer and optimal. Geometrically the cut slices the fractional apex off the triangle.
Problem. Suppose a rounding heuristic hands you an integer solution worth \(40\) before any branching. How does this help?
Solution. Set \(\underline{z} = 40\) at the start. Now any node whose LP value is \(\le 40\) is fathomed immediately by the bound rule. In the running example this would close the \(x_1 \le 3\) branch (value \(39\)) at once, shrinking the tree. A strong initial incumbent is one of the cheapest ways to speed the search.
Chapter Summary
Reason about families of solutions at once instead of listing all \(2^n\) candidates.
Solve each node's LP, split on a fractional variable, and close nodes by three rules.
Fractional \(x_j=f\) splits into \(x_j \le \lfloor f\rfloor\) and \(x_j \ge \lceil f\rceil\) — exhaustive, disjoint.
Infeasible, bounded out (\(z_{\text{LP}} \le \underline{z}\)), or integer — then no branching needed.
Depth-first vs best-first; a good early incumbent prunes hard. IP is NP-hard.
Gomory cuts \(\sum_j f_j x_j \ge f_0\) trim fractional vertices; branch-and-cut blends both.
Problems
Work each tree or cut carefully, stating the rule that closes every node. Difficulty rises down the list.
- Explain why listing all solutions is impractical for a 0–1 problem with \(40\) variables.
- State the three fathoming rules for a maximization problem and give a one-line justification of each.
- A node's LP optimum is \((1.5,\ 4,\ 2.25)\). List the possible branching variables and the two subproblems for each.
- Define the incumbent and explain how it interacts with the bound rule.
- Why are the two branches \(x_j \le \lfloor f\rfloor\) and \(x_j \ge \lceil f\rceil\) exhaustive and mutually exclusive?
- Contrast depth-first and best-first node selection in terms of memory use and speed of proving optimality.
- For the running example, redraw the branch-and-bound tree assuming an initial incumbent of \(40\); which nodes are now pruned immediately?
- State the Gomory fractional cut in terms of the fractional parts \(f_j\) and \(f_0\), and explain why no integer point is removed.
- Explain in words how branch-and-cut differs from pure branch and bound and from pure cutting planes.
- Solve by branch and bound: \(\max 3x_1 + 2x_2\) s.t. \(x_1 + x_2 \le 4,\ x_1 \le 2,\ x_1,x_2 \ge 0\) integer. Show the tree and the optimum.
- Solve by branch and bound: \(\max 5x_1 + 4x_2\) s.t. \(6x_1 + 4x_2 \le 24,\ x_1 + 2x_2 \le 6,\ x_1,x_2 \ge 0\) integer. Report the LP relaxation value, the integer optimum, and the integrality gap.
- The LP relaxation of a knapsack fills the last item fractionally at \(x_k = 0.6\). Describe the two branches, and argue why branching on \(x_k\) must eventually fathom both children.