A search tree, an LP at each node, and the bound that prunes it.
Chapter: 0b — MIP theory · lesson id mip-branchbound · theory lesson
Branch-and-bound is the algorithm every commercial MIP solver runs underneath the GUI. The idea is half a century old (Land & Doig, 1960) and has been refined into a remarkably effective beast through cuts, heuristics, and presolve. The skeleton is simple enough to write on a napkin.
Convention for the rest of this lesson: we write $Z$ for the LP relaxation's objective value at a node, and $Z^{*}$ for the current incumbent's objective (the best integer-feasible value seen so far). This matches the notation in most OR textbooks and in the HiGHS / CPLEX / Gurobi documentation.
Maintain a tree of subproblems. The root is the original MIP. At each node:
$1.$ Solve the $LP\ relaxation$ of the subproblem. Call its optimum $Z$.
$2.$ If the LP is infeasible, $prune$ this branch.
$3.$ If $Z$ is worse than the incumbent $Z^{}$ (i.e. $Z \geq Z^{}$ for a min, or $Z \leq Z^{}$ for a max), $prune\ by\ bound$ — no integer point in this subtree can beat $Z^{}$.
$4.$ If the LP solution is integer-feasible (the relaxed variables all happen to come out integer), it is an integer feasible point for the original MIP. If $Z$ beats $Z^{}$, update the incumbent: $Z^{} \leftarrow Z$.
$5.$ Otherwise, pick a variable $x_{j}$ whose LP value $\tilde{x}{j}$ is fractional and $branch$: create two child subproblems, one with $x{j} \leq \lfloor \tilde{x}{j} \rfloor$ and one with $x{j} \geq \lceil \tilde{x}_{j} \rceil$. Add them to the queue.
Repeat until the queue is empty. The incumbent $Z^{*}$ at termination is the proven optimum.
Consider $\max\ 5 x_{1} + 4 x_{2}$ s.t. $6 x_{1} + 4 x_{2} \leq 24$, $x_{1} + 2 x_{2} \leq 6$, $x_{1}, x_{2} \geq 0$ and integer.
$Root:$ LP relaxation has its optimum at the intersection of the two binding constraints: $x_{1} = 3$, $x_{2} = 1.5$, $Z = 21$. $x_{2}$ is fractional, so branch on $x_{2}$. Add child nodes for $x_{2} \leq 1$ and $x_{2} \geq 2$.
$Node\ x_{2} \geq 2:$ LP gives $x_{1} = 2$, $x_{2} = 2$, $Z = 18$. Integer! Set incumbent $Z^{*} = 18$.
$Node\ x_{2} \leq 1:$ LP gives $x_{1} = 10/3 \approx 3.33$, $x_{2} = 1$, $Z = 62/3 \approx 20.67$. $x_{1}$ is fractional; branch on it. Add $x_{1} \leq 3$ and $x_{1} \geq 4$ (both still under $x_{2} \leq 1$).
$Node\ x_{2} \leq 1, x_{1} \leq 3:$ LP gives $x_{1} = 3$, $x_{2} = 1$, $Z = 19$. Integer. Update $Z^{*} = 19$.
$Node\ x_{2} \leq 1, x_{1} \geq 4:$ LP gives $x_{1} = 4$, $x_{2} = 0$, $Z = 20$. Integer. Update $Z^{*} = 20$. This is the new incumbent.
The queue is empty. The tree closes with $Z^{*} = 20$ as the proven integer optimum at $(x_{1}, x_{2}) = (4, 0)$.
[network-graph diagram: Branch-and-bound search tree for the worked trace. The incumbent (Z = 20) is marked in rust; the other integer-feasible nodes are filled green; no node remained unresolved.]*
Read the tree top-to-bottom. The root's LP is $21$, an upper bound on the integer optimum since we are maximising. Each child further restricts the feasible region and so its LP value is no greater than its parent's. Three of the five subproblems happen to have integer LP solutions and become leaves; the incumbent only improves as the search progresses.
Every solver records the search as a $node\ log$ — one row per significant event. The same trace from above, expressed as a log:
$$ \begin{array}{|c|l|c|c|c|c|c|} \hline \textbf{Step} & \textbf{Event} & \textbf{Nodes} & \textbf{Queue} & Z_{\text{UB}} & Z^{*} & \textbf{Gap} \ \hline 1 & \text{Root LP solved, branch on } x_{2} & 1 & 2 & 21.00 & -\infty & - \ 2 & \text{Node } x_{2} \geq 2:\ \text{LP} = 18,\ \text{integer} & 2 & 1 & 21.00 & 18 & 16.7% \ 3 & \text{Node } x_{2} \leq 1:\ \text{LP} = 20.67,\ \text{branch on } x_{1} & 3 & 2 & 20.67 & 18 & 14.8% \ 4 & \text{Node } x_{2} \leq 1, x_{1} \leq 3:\ \text{LP} = 19,\ \text{integer} & 4 & 1 & 20.67 & 19 & 8.8% \ 5 & \text{Node } x_{2} \leq 1, x_{1} \geq 4:\ \text{LP} = 20,\ \text{integer} & 5 & 0 & 20.00 & 20 & 0.0% \ \hline \end{array} $$
Three quantities to track row-by-row:
Step 1 logs the root. There is no incumbent yet so the gap is undefined. Step 2 immediately produces an integer solution at $Z = 18$ — the incumbent is born. The remaining steps tighten the upper bound (by exploring the $x_{2} \leq 1$ subtree whose LP is $20.67$, not the looser parent $21$) and improve the incumbent. Step 5 closes the gap: the queue is empty and the upper bound has dropped to the incumbent's value.
$Root\ LP.$ The two constraint lines meet at $x_{1} = 2$, $x_{2} = 1.5$. Both constraints bind and the objective $4 x_{1} + 3 x_{2} = 12.5$ is maximal there. So $Z = 12.5$ and $x_{2}$ is fractional. Branch on $x_{2}$: add subproblems $x_{2} \leq 1$ and $x_{2} \geq 2$.
$Node\ x_{2} \geq 2.$ With $x_{2} = 2$ as the lower bound: $3 x_{1} + 4 \leq 9 \Rightarrow x_{1} \leq 5/3$, and $x_{1} + 4 \leq 5 \Rightarrow x_{1} \leq 1$. The tighter constraint wins: $x_{1} = 1$, $x_{2} = 2$, $Z = 4 + 6 = 10$. Integer — set incumbent $Z^{*} = 10$.
$Node\ x_{2} \leq 1.$ The LP optimum is on the boundary $3 x_{1} + 2 x_{2} = 9$. Setting $x_{2} = 1$ (the upper bound for this subtree) gives $3 x_{1} = 7 \Rightarrow x_{1} = 7/3 \approx 2.33$. $Z = 28/3 + 3 = 37/3 \approx 12.33$. Fractional in $x_{1}$. Branch on $x_{1}$: add $x_{1} \leq 2$ and $x_{1} \geq 3$.
$Node\ x_{2} \leq 1, x_{1} \leq 2.$ At $x_{1} = 2$, $x_{2} = 1$ is feasible: $6 + 2 = 8 \leq 9$, $2 + 2 = 4 \leq 5$. $Z = 8 + 3 = 11$. Integer. $Z^{*} \leftarrow 11$.
$Node\ x_{2} \leq 1, x_{1} \geq 3.$ At $x_{1} = 3$, $3 \cdot 3 + 2 x_{2} = 9 + 2 x_{2} \leq 9 \Rightarrow x_{2} \leq 0$. So $x_{1} = 3$, $x_{2} = 0$. $Z = 12$. Integer. $Z^{*} \leftarrow 12$. Queue empty.
Five nodes processed in total. Proven integer optimum: $Z^{*} = 12$ at $(x_{1}, x_{2}) = (3, 0)$.
[network-graph diagram: The full search tree. The incumbent (Z = 12 at the lower-right) was the last node found.]*
[feasible-region diagram: LP feasible region with the four integer feasible points marked at their objective values.]
Worst-case the tree is exponential. In practice three things keep it small:
$\bullet$ $Good\ bounds$. Strong formulations (small integrality gap) mean every node's LP gives a tight bound, and many branches prune immediately.
$\bullet$ $Cuts$. The solver adds extra linear inequalities that are valid for all integer-feasible points but cut off the current fractional LP optimum. Branch-and-bound + cuts is called $branch$-$and$-$cut$ and is what every modern solver actually runs.
$\bullet$ $Heuristics$. The solver tries fast heuristics (rounding, feasibility pump, RINS) to find an early incumbent, which sharpens pruning for the rest of the search.
Quick check. A min-MIP branch-and-bound run reports a node with LP value $25$ and the current incumbent is $20$. What happens to this node?
Recap.
Read this through MCP: read with path: "lessons/mip-branchbound", or resource hlpl://lessons/mip-branchbound.