Branch and bound
Branch and bound is a general method for solving discrete and combinatorial optimization problems. It represents the feasible region as a collection of progressively smaller subproblems, associates each subproblem with a bound on its attainable objective value, and removes subproblems whose bounds establish that they cannot contain a better solution than the best one already known. The method thereby performs an implicit enumeration of the feasible solutions without ordinarily constructing every member of that set.
For a minimization problem, branch and bound maintains an incumbent objective value (U), obtained from the best feasible solution encountered, and a lower bound (L(N)) for each active search node (N). A node is eliminated when it is infeasible, when its lower bound satisfies (L(N)\geq U), or when its subproblem has been solved completely. Nodes not eliminated are divided into descendant subproblems. The corresponding inequalities are reversed for a maximization problem.
Branch and bound is not a single algorithm with a fixed search order or bounding formula. It is an organizing framework whose computational behavior depends on the mathematical relaxation, the branching disjunction, the treatment of incumbents, and the policy governing the active nodes.
Mathematical formulation
Consider the optimization problem
[ z^\star=\min {f(x):x\in X}, ]
where (X) contains discrete restrictions that make direct continuous optimization insufficient. A node (N) represents a subset (X_N\subseteq X), and the collection of current nodes covers every feasible solution not already excluded. A valid lower bound satisfies
[ L(N)\leq \min{f(x):x\in X_N}. ]
If a feasible point (\hat{x}) has already produced the incumbent value (U=f(\hat{x})), then every node satisfying (L(N)\geq U) can be discarded. No point in such a node can improve the incumbent.
Branching replaces a node (N) by descendant nodes (N_1,\ldots,N_k) satisfying
[ X_N=X_{N_1}\cup\cdots\cup X_{N_k}. ]
The descendant regions may overlap, although most implementations employ disjoint or nearly disjoint partitions. In a mixed-integer linear program, a fractional variable (x_j) with relaxation value (\bar{x}_j) commonly induces the disjunction
[ x_j\leq \lfloor\bar{x}_j\rfloor \qquad\text{or}\qquad x_j\geq \lceil\bar{x}_j\rceil. ]
The linear programming relaxation supplies a lower bound when the integrality conditions are omitted from a minimization problem. If the relaxation solution already satisfies every discrete restriction, it is feasible for the original problem and can replace the incumbent when its objective value is smaller.
The difference between the incumbent and the strongest active lower bound is the absolute optimality gap,
[ G=U-\min_{N\in\mathcal A}L(N), ]
where (\mathcal A) denotes the active-node set. A zero gap establishes optimality, subject to the numerical conventions used in the relaxation solver. Relative gaps normalize this difference by a scale derived from the incumbent or from both bounds.
Historical development
The framework developed from earlier methods of implicit enumeration and from the use of relaxations in discrete optimization. In 1960, Ailsa Land and Alison Doig published a method for solving discrete programming problems by partitioning the feasible region and using bounds derived from continuous subproblems. Their formulation contained the principal elements later associated with branch and bound.
In 1962, Land, Doig, and You Watanabe extended the computational analysis to integer models of ship loading and capacity allocation. Their study treated partial cargo manifests as nodes and used continuous capacity relaxations to bound the value of incomplete load plans. The manifest representation was specific to that application, while its node partitioning and incumbent comparisons were instances of the general branch-and-bound framework.
The term became established through work on the travelling salesperson problem. In 1963, John Little, Katta Murty, Dura Sweeney, and Caroline Karel described a branch-and-bound algorithm based on reduced cost matrices and tour exclusions. Their formulation demonstrated how problem-specific bounds and branching rules could transform the same general search framework into a specialized exact algorithm.
Later research integrated branch and bound with the simplex method, cutting planes, preprocessing transformations, and increasingly systematic rules for selecting branches. These developments produced branch and cut, in which valid inequalities strengthen node relaxations during the search, and branch and price, in which node relaxations are solved through column generation.
Search tree and node processing
The subproblems generated by branching form a rooted search tree. The root represents the original optimization problem, while each edge records an additional restriction. A path from the root therefore represents an accumulating sequence of decisions. A leaf can correspond to an infeasible region, a region excluded by its bound, or a region whose optimal feasible solution has been identified.
Node selection affects memory consumption and the order in which bounds and incumbents are discovered. Best-bound search selects a node whose relaxation has the most favorable bound, which concentrates computation on the portion of the tree that currently determines the global dual bound. Depth-oriented search continues along a recently created path, which ordinarily requires fewer simultaneously stored nodes and can reach complete feasible assignments early. Hybrid policies alternate between these behaviors according to the state of the search.
The branching rule influences both the number of descendants and the strength of their relaxations. In integer programming, strong branching temporarily evaluates candidate disjunctions by solving or partially solving the associated descendant relaxations. Pseudocost methods instead estimate the objective degradation associated with earlier branches on the same variables. Reliability branching combines direct evaluation with accumulated estimates, using explicit trial solves until the historical information reaches a prescribed level of stability.
An incumbent may arise when a node relaxation is integral, when a specialized primal construction produces a feasible point, or when an existing feasible assignment is improved by a local transformation. Incumbent discovery does not itself prove optimality. Its principal formal effect is to strengthen the cutoff value against which active-node bounds are compared.
Bounding and relaxation quality
A bound is valid when it does not exclude an attainable objective value, but validity alone does not determine computational usefulness. A weak lower bound leaves a large difference between the relaxation and the integer optimum, causing many nodes to remain eligible for exploration. A stronger relaxation can eliminate larger portions of the tree, although its evaluation may require greater computation at each node.
For mixed-integer linear optimization, the basic bound comes from the linear relaxation. Additional valid inequalities can reduce the relaxation region without removing integer-feasible points. When such inequalities describe facets of the convex hull of feasible solutions, they can substantially alter the geometry encountered by the search.
In the travelling salesperson problem, bounds can be obtained from assignment relaxations, minimum spanning structures, or constrained one-tree constructions. These relaxations retain enough of the tour structure to produce informative objective bounds while omitting conditions that make the full problem difficult. Branching then restores the omitted distinctions by dividing the admissible tours according to selected edges or other structural decisions.
For the knapsack problem, a fractional relaxation permits the final selected item to be divided. The resulting value bounds every integral packing represented by the node. Since the fractional relaxation has a direct ordered solution, it illustrates the common relationship between inexpensive bounds and a potentially large enumeration tree.
Correctness and termination
Correctness follows from coverage and valid elimination. The active nodes, together with nodes already solved, continue to cover every feasible solution not excluded by a logically valid argument. Infeasibility removes no feasible point, while bound-based elimination removes only regions unable to improve the incumbent. When no active node remains, the incumbent is therefore globally optimal.
Finite termination holds when branching produces a finite tree and every node is eventually selected or eliminated. Bounded integer programs with finite variable domains satisfy this condition under ordinary variable branching. Problems with unbounded domains or continuously parameterized disjunctions require additional assumptions to establish finiteness.
Numerical implementations distinguish mathematical bounds from floating-point approximations. Relaxation tolerances affect whether a variable is treated as integral and whether a node bound is considered equal to the incumbent. These conventions preserve practical consistency by incorporating explicit feasibility and optimality tolerances, but they make the reported certificate dependent on the numerical model and arithmetic environment.
Computational complexity
Branch and bound does not change the worst-case complexity of the underlying NP-hard problems to which it is commonly applied. A search tree can contain exponentially many nodes, and specially constructed instances can force enumeration of a large fraction of that tree. Its practical performance instead depends on whether the chosen relaxations and disjunctions expose enough structure to eliminate broad regions early.
The size of a branch-and-bound proof also has an interpretation in proof complexity. Each fathomed node contributes a local certificate that its region is infeasible or cannot improve the incumbent. The completed tree forms a global certificate assembled from these local arguments. Different branching systems can yield substantially different certificate sizes even when they operate on the same optimization model.
Parallel implementations distribute active nodes among processors while sharing incumbent values and global bounds. The resulting search order differs from that of a serial execution because discoveries occur asynchronously. This can produce either a smaller or a larger explored tree, since an early incumbent may strengthen pruning while delayed bound information may preserve nodes that a serial ordering would already have removed.