Branch and Bound
Also known as: B&B, Land-Doig Algorithm, Implicit Enumeration, Dal ve Sınır
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.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
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.
Strengths & limitations
- 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).
- 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.
Frequently asked
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.
Sources
- Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129 ↗
How to cite this page
ScholarGate. (2026, June 2). Branch and Bound. ScholarGate. https://scholargate.app/en/optimization/branch-and-bound
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Constraint ProgrammingOptimization↔ compare
- Dynamic ProgrammingOptimization↔ compare
- Integer ProgrammingOptimization↔ compare