Takeaway

Branch-and-bound solves discrete optimization by recursively partitioning the search space and pruning subproblems using bounds from relaxations.

The problem (before → after)

  • Before: Exhaustive search is exponential.
  • After: Tight relaxations and clever branching prune vast portions of the tree.

Mental model first

Like solving a maze by dividing corridors and sealing off paths that can’t possibly lead to a shorter exit than your current best.

Just-in-time concepts

  • Relaxation (LP) gives an optimistic bound; integrality gap guides pruning.
  • Branching strategies (variable, strong branching).
  • Node selection (best-bound, depth-first) and cutting planes.

First-pass solution

Solve LP relaxation; if integer, update incumbent; else branch on fractional variable; prune nodes with bound worse than incumbent.

Iterative refinement

  1. Cutting planes tighten relaxations (branch-and-cut).
  2. Heuristics find good incumbents early.
  3. Warm starts and presolve reduce problem size.

Principles, not prescriptions

  • Invest in strong bounds and good branching to shrink trees.
  • Integrate cuts and heuristics adaptively.

Common pitfalls

  • Weak relaxations cause explosion.
  • Poor branching leads to imbalanced trees and slowdowns.

Connections and contrasts

  • See also: [/blog/benders-decomposition], [/blog/convex-optimization].

Quick checks

  1. Why LP relaxations? — Provide fast bounds for pruning.
  2. What is an incumbent? — Best feasible integer solution so far.
  3. Why cuts? — Tighten feasible region without excluding integers.

Further reading

  • Land & Doig (1960s); modern MILP solvers’ docs