Branch & Bound

Bound each subproblem by its relaxation, then prune what cannot win.

The idea

Branch & bound is an exact algorithm for integer programs: it ends holding an optimal solution together with a proof that nothing better exists, and it gets there without inspecting every feasible point — there are far too many to enumerate.

Take a maximization $\max\{c^{\top}x : x \in S\}$ over an integer feasible set $S$. The method splits $S$ into smaller subproblems, the nodes of a search tree, and carries two numbers as it goes. The incumbent $L$ is the objective value of the best integer-feasible solution found so far, so the optimum is at least $L$. Each node gets an upper bound $U$ from a relaxation: drop the requirement that the variables be integers and solve the easier problem that remains. Dropping a requirement can only enlarge the feasible set, so the relaxed optimum is at least the node's true optimum, and $U$ is a genuine ceiling on every solution inside the node.

Proposition (Pruning is safe).

Let a node have relaxation optimum $U$, and let $L$ be the incumbent value. Every integer-feasible solution in the node has objective value at most $U$; so if $U \le L$, the node contains no solution better than the incumbent, and it can be discarded without being searched.

The proposition is what lets the search skip most of the tree: a node is opened only when its bound leaves room for improvement.

Algorithm.

Algorithm: Branch & Bound Input: the maximization max{cᵀx : x ∈ S} over the integer feasible set S Output: an optimal solution, with proof that nothing better exists 1. make the whole problem the one live node; L = −∞ // every solution beating L lies inside some live node 2. if no live node remains, return the incumbent // nothing better exists, so it is optimal 3. pick a live node, solve its relaxation; U = the relaxed optimum // U: the node's upper bound 4. resolve the node if the relaxation settles it: if the relaxation is infeasible, discard the node, go to step 2 // the node holds no solutions if U ≤ L, prune: discard the node whole, unexamined, go to step 2 // nothing in it beats the incumbent if the relaxed optimum is integral and exceeds L, it becomes the incumbent, L = its value; discard the node, go to step 2 5. otherwise branch: split the node into children holding all its integer points between them, each a new live node, and go to step 2

Ways to work on it

• Walkthrough. Search for an integer optimum by bounding and pruning a tree of subproblems.
• Practice. Decide whether a node should be pruned or branched on.
• Hardest. Run the bounding logic across leaves to certify the optimum.

Not sure where to start? Take the ten-question placement test.