An exact algorithmic paradigm for combinatorial optimisation that systematically explores a tree of candidate solution subsets, using bounds from relaxations of the problem to prune any branch that provably cannot contain a solution better than the best one found so far. Introduced by Land and Doig in 1960 for integer programming, branch and bound guarantees optimality while often avoiding exhaustive enumeration, and remains the backbone of modern mixed-integer programming and constraint solvers.
Semantic Classification
Content
Definition
Branch and bound organises the search for an optimal discrete solution as a tree. Branching partitions the current set of candidate solutions into smaller subsets — for instance, fixing an integer variable to lie below or above a fractional value. Bounding computes, for each subset, an optimistic bound on the best objective value it could contain, typically by solving a cheap relaxation (linear programming relaxation, Lagrangian relaxation, or a problem-specific bound). Any node whose bound is no better than the incumbent — the best complete solution found so far — is pruned, along with the entire subtree beneath it.
The method is exact: when the tree is exhausted, the incumbent is provably optimal, and at any point the gap between incumbent and best outstanding bound certifies how far from optimal the current answer can be. Its practical performance therefore hinges on bound tightness, branching variable selection, and node exploration order (best-first, depth-first, or hybrids), which is where decades of solver engineering — and, recently, learned branching policies — concentrate.
In this graph, branch and bound is a core component of Combinatorial Optimisation and of practical Constraint Solver engines, where it generalises backtracking search over Constraint Satisfaction problems to optimisation by treating the objective as a progressively tightening constraint. It contrasts with Dynamic Programming, which exploits overlapping subproblem structure rather than pruning by bounds, and the two are frequently combined.
Technical Details
-
Canonical applications: mixed-integer linear programming (MILP), travelling salesman (Held-Karp bounds), knapsack, job-shop scheduling, and MAP inference in graphical models.
-
Branch and cut / branch and price: modern MILP solvers (CPLEX, Gurobi, SCIP, CBC) interleave cutting planes and column generation with the branch-and-bound tree; presolve, heuristics for early incumbents, and conflict learning further shrink the tree.
-
Search strategies: best-first order minimises nodes expanded but is memory-hungry; depth-first finds incumbents quickly with O(depth) memory; solvers typically dive for incumbents then switch strategy.
-
Complexity: worst case remains exponential — the paradigm does not evade NP-hardness — but strong bounds routinely reduce practical instances from astronomically many candidates to thousands of explored nodes.
-
Parallelism: subtrees are naturally independent, enabling parallel and distributed tree search, though load balancing and sharing of incumbents/pseudo-costs are non-trivial; the UG framework (v1.0) parallelises branch and bound over shared- and distributed-memory machines with SCIP as the base solver.
Current Landscape
-
Solver releases: the SCIP Optimization Suite 10.0 (November 2025) added an exact rational MILP solving mode, cut-based conflict analysis, a new infeasibility-explanation tool, and improved branching strategies, with maintenance release 10.0.2 following in April 2026; SCIP remains one of the fastest non-commercial MIP/MINLP solvers and the standard research testbed because its branching and cut-selection internals are open, unlike Gurobi and CPLEX.
-
Nonlinear extension: Gurobi 12 added support for general nonlinear constraints via dynamic outer approximation, treating global MINLP as a spatial branch-and-bound extension of MILP branch and bound.
-
Learned branching: machine-learning-guided tree search is an active research front — SORREL (AAAI 2025) applies reinforcement learning over suboptimal demonstrations to variable branching, and Collab-Solver (2025) jointly learns cut-selection and branching policies as a Stackelberg game, reporting roughly 50% solving-time improvement over default SCIP on benchmark sets.
Sources:
-
https://optimization-online.org/wp-content/uploads/2025/11/scipopt-100.pdf