Branch and Bound
A worked integer-programming search tree: maximize 3x + 2y subject to 2x + y ≤ 4, x + 2y ≤ 4, and nonnegative integer x,y. The LP relaxation at P₀ gives (4/3,4/3) and upper bound 20/3. Branch on x: x ≤ 1 leads to P₁ with LP solution (1,3/2) and bound 6; x ≥ 2 leads to P₂.
Explore the left subtree first. Splitting P₁ on y produces P₃ with y ≤ 1 and P₄ with y ≥ 2. Step 1: P₃ gives the integer solution (1,1), setting the incumbent to L = 5. Step 2: P₄ has LP solution (0,2) and upper bound U = 4, so it cannot improve the incumbent and is pruned. Step 3: P₂ gives the integer solution (2,0), improving L to 6. Every leaf is resolved, proving optimality. The numbered annotations show this visitation order; P labels identify subproblems.
For maximization, U is a subproblem's LP upper bound and L is the best feasible integer objective found so far. A node with U ≤ L cannot improve the incumbent. Pruning on equality finds one optimum; enumerating every optimal solution requires retaining tied branches. Search order affects the size of the tree: exploring P₂ first would set L = 6 immediately and prune P₁ without its second split.
Download
Code
branch-and-bound.typ (54 lines)
#import "@preview/cetz:0.5.2": canvas, draw
#import draw: circle, content, line
#set page(width: 500pt, height: auto, margin: (x: 20pt, y: 8pt), fill: none)
#set text(font: "Avenir Next", size: 12pt)
#set par(leading: 0.55em)
#let objective(x, y) = 3 * x + 2 * y
#let feasible(x, y) = x >= 0 and y >= 0 and 2 * x + y <= 4 and x + 2 * y <= 4
// Root, x >= 2, x <= 1, then the two children of x <= 1.
#let lp_points = ((4 / 3, 4 / 3), (2, 0), (1, 3 / 2), (1, 1), (0, 2))
#align(center)[#box(inset: (x: 10pt, y: 7pt), radius: 5pt, fill: rgb("#cdd3da"))[
#grid(
columns: (auto, auto),
column-gutter: 10pt,
row-gutter: 5pt,
align: left + horizon,
[*Objective*], [$max z = 3x + 2y$],
[*Constraints*], [$2x+y <= 4, quad x+2y <= 4, quad x,y in ZZ_(>=0)$],
)
]
]
#v(4pt)
#align(center)[#canvas(length: 1pt, {
let nodes = (
(name: "p0", pos: (0, 0), label: $P_0$, fill: none),
(name: "p1", pos: (-85, -105), label: $P_1$, fill: none),
(name: "p2", pos: (90, -105), label: $P_2$, fill: rgb("#c6d8d2")),
(name: "p3", pos: (-145, -220), label: $P_3$, fill: rgb("#c6d8d2")),
(name: "p4", pos: (-25, -220), label: $P_4$, fill: rgb("#ead3c5")),
)
for node in nodes {
circle(node.pos, radius: 19, fill: node.fill, stroke: 1.2pt, name: node.name)
content(node.pos, text(size: 21pt, node.label))
}
for (parent, child, label, offset) in (
("p0", "p1", $x <= 1$, (-23, 8)),
("p0", "p2", $x >= 2$, (23, 8)),
("p1", "p3", $y <= 1$, (-24, 0)),
("p1", "p4", $y >= 2$, (24, 0)),
) {
let edge_name = parent + "-" + child
line(parent, child, stroke: 1pt, mark: (end: "stealth", scale: 0.7), name: edge_name)
content((rel: offset, to: edge_name + ".mid"), label)
}
content((0, 44), align(center)[*LP relaxation*\ $(x,y)=(4 \/ 3,4 \/ 3), quad U=20 \/ 3$])
content((-114, -105), align(right)[$(1,3 \/ 2)$\ $U=6$], anchor: "east")
content((120, -105), [*3 Incumbent*\ $(2,0), quad L=6$], anchor: "west")
content((-145, -260), align(center)[*1 Integer*\ $(1,1), quad L=5$])
content((-15, -260), align(center)[*2 Prune*\ $(0,2), quad U=4 <= 5$])
})]
#v(12pt)
#align(center)[*Optimal:* $(x,y)=(2,0), quad z^*=6$]