Branch and Bound
- Introduced by
- Ailsa Land & Alison Doig
- Year
- 1960
- Type
- Exact combinatorial optimization algorithm
- Family
- Mathematical programming
What does it do?
Branch and Bound is a systematic exact algorithm for combinatorial and integer optimization problems, introduced by Ailsa Land and Alison Doig in 1960.
It organizes the search space as a tree of subproblems, uses relaxation-derived upper bounds to prune branches that cannot improve the best known solution, and guarantees finding a globally optimal integer solution. It is the backbone of modern mixed-integer programming solvers used in operations research, logistics, scheduling, and engineering design.
The intuition behind the method
Imagine searching for the highest-valued item hidden in a vast maze of rooms. Instead of checking every room, you estimate the maximum possible value reachable from each corridor before entering it. If that ceiling is lower than the best item you already hold, you skip the entire corridor without looking inside. Branch and Bound works the same way: it splits the problem into smaller pieces, computes optimistic upper bounds for each piece, and immediately discards any piece that provably cannot beat the current best solution.
History
Land and Doig published the foundational Branch and Bound paper in Econometrica in 1960, framing it as an automatic method for discrete programming. Little et al. (1963) applied the technique to the traveling salesman problem, cementing its role in combinatorial optimization. Dakin (1965) introduced LP-relaxation branching, the form most commonly used today. Subsequent decades saw the integration of cutting planes (branch-and-cut) and column generation (branch-and-price), making Branch and Bound the engine inside all major commercial integer programming solvers.
When to use it
Use Branch and Bound when you must find the provably optimal solution to a mixed-integer or pure-integer linear program and cannot accept an approximate answer. It assumes the problem can be formulated with linear (or convex) relaxations that provide useful bounds. It is less suitable for very large instances where the enumeration tree explodes, for nonlinear integer programs without tight relaxations, or for real-time settings where computation time is strictly limited. In such cases, heuristics or metaheuristics may be preferred.
Limitations and considerations
- Worst-case complexity is exponential; on poorly structured instances the tree can grow prohibitively large.
- Performance is highly sensitive to the choice of branching variable and node selection strategy.
- Requires a tractable relaxation that provides meaningful upper bounds; weak bounds lead to minimal pruning.
- Memory requirements can be substantial when many open nodes must be stored simultaneously.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Guarantees global optimality for integer and combinatorial programs.
- Dramatically reduces search through bound-based pruning — often only a tiny fraction of the full enumeration tree is explored.
- Flexible: can incorporate cutting planes (branch-and-cut) or heuristic bounds (branch-and-price) for further efficiency.
- Widely implemented in mature commercial solvers (CPLEX, Gurobi) and open-source tools (GLPK, CBC).
Applications
- Airline crew scheduling and fleet assignment in operations research.
- Supply-chain network design and facility location problems.
- VLSI circuit layout and register allocation in computer engineering.
- Protein structure prediction and genome assembly in computational biology.
- Financial portfolio optimization with cardinality constraints.
How it works
How it works
The algorithm begins by solving a relaxed version of the problem — typically the LP relaxation — that ignores the integrality constraints. This relaxation yields an upper bound on the true optimal value because every feasible integer solution is also feasible in the relaxation. If the relaxed solution happens to be integer-valued, the problem is solved immediately.
Formula
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}When the relaxed solution contains a fractional variable, the algorithm partitions the feasible region by adding complementary constraints that force the variable to either its floor or ceiling. Each partition creates a new child node in the search tree, effectively splitting one subproblem into two smaller subproblems with tighter domains.
Formula
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilEach active node receives its own LP relaxation bound. A node whose bound does not exceed the best integer solution found so far — called the incumbent — cannot contain a better solution, so it is pruned. Tight bounds are critical: the tighter the bound, the fewer nodes need to be explored.
Formula
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}A node is fathomed (permanently closed) under three conditions: its relaxation is infeasible, its bound is no better than the incumbent, or its relaxed solution is already integer-feasible. In the last case the incumbent is updated if the new solution improves it. The algorithm terminates when all nodes are fathomed, at which point the incumbent is the global optimum.
Formula
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)Common pitfalls
- Choosing the branching variable poorly (e.g., always branching on the first fractional variable) often leads to deep, unbalanced trees and slow convergence.
- Ignoring valid inequalities (cutting planes) means missing the opportunity to tighten relaxation bounds significantly.
- Premature termination with a suboptimality gap that is not reported as such can mislead practitioners into treating a near-optimal solution as exact.
- Applying Branch and Bound to nonlinear or non-convex relaxations without specialized convexification may yield invalid bounds and incorrect results.
Frequently asked questions
How does Branch and Bound differ from exhaustive enumeration?
Exhaustive enumeration evaluates every feasible integer solution explicitly, which is computationally infeasible for large problems. Branch and Bound avoids this by computing relaxation-based upper bounds at each node of the search tree and pruning entire subtrees whenever the bound cannot exceed the best solution already found. In practice, only a small fraction of the tree is ever examined.
What is the role of the LP relaxation in Branch and Bound?
The LP relaxation drops integrality constraints, making the problem solvable in polynomial time by the simplex or interior-point method. Its optimal value serves as an upper bound for the corresponding integer sub-problem. When this bound is tight — close to the true integer optimum — fewer branches need to be explored. Tighter relaxations, often achieved by adding valid inequalities, dramatically accelerate the overall algorithm.
When should I use Branch and Bound versus a metaheuristic like genetic algorithms?
Choose Branch and Bound when you require a certificate of optimality and can afford the computation time. It is ideal for medium-sized problems with well-structured LP relaxations. Metaheuristics are preferable when the problem is extremely large, lacks a useful relaxation, or must be solved within a tight time budget where a near-optimal solution is acceptable. Many practitioners combine both: use Branch and Bound with an early-termination gap tolerance.
Related methods
Sources
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
Open DOI referenceCopied.