Branch-and-bound is a general framework for solving mathematical optimization problems by systematically dividing them into smaller subproblems and discarding those that cannot contain a better solution than one already found. Its defining feature is the combination of branching, which organizes possible solutions into a search tree, and bounding, which establishes limits on the quality of solutions within each part of that tree. Unlike exhaustive enumeration, it can exclude large groups of possibilities without examining them individually.
The framework is especially important in integer programming, where some or all decision variables must take integer values, and in combinatorial problems involving selections, assignments, sequences, or networks. It also underlies methods for continuous nonconvex optimization. A successfully completed branch-and-bound computation provides both an optimal solution and a justification that no better solution exists, subject to the validity of its bounds and its numerical calculations.
Branch-and-bound is not a single fixed algorithm. Its practical behavior depends on how subproblems are formed, how tightly they are bounded, how promising solutions are discovered, and which parts of the search tree are explored first. Modern implementations integrate relaxation methods, inference, cutting planes, heuristics, and parallel processing, often making the search tree only one component of a much larger optimization system.
Mathematical foundations and terminology
Consider a minimization problem
where is the feasible set and is the objective function. A node in a branch-and-bound tree represents a restricted feasible set . The root represents the original problem. Branching replaces a node by children whose feasible sets collectively cover its remaining possibilities:
The children are often disjoint, although coverage rather than disjointness is the essential requirement for preserving correctness.
For minimization, a node bound must satisfy
An incumbent is the best feasible solution found so far, with objective value . Because it is feasible, it supplies an upper bound on the optimum: . If , no solution represented by node can improve the incumbent, so that node may be discarded. This operation is called pruning or fathoming.
The direction of the inequalities reverses for maximization. A node then needs an upper bound on attainable objective values, while the incumbent supplies a lower bound. This distinction is important because the word “bound” may refer either to information obtained from a subproblem or to the value of a known feasible solution. The terms primal bound and dual bound are also used: for minimization, the incumbent is a primal upper bound, while suitable node relaxations provide dual lower bounds.
An active node is a subproblem that has not yet been completely processed or discarded. Its descendants need not have been generated. The tree therefore represents an implicit enumeration: a single unprocessed node may stand for an enormous number of candidate solutions. Bounds allow that entire collection to be rejected at once.
If active nodes cover every unresolved possibility, a global lower bound can be formed as
where is the active-node set and the minimum over an empty set is taken as . For a finite incumbent, this gives . The interval between these values measures what remains unproved, rather than how far the incumbent necessarily lies from the true optimum.
The basic procedure and its correctness
A basic branch-and-bound algorithm begins with the root node, an active-node collection, and no incumbent. For minimization, the initial incumbent value is conventionally . A feasible solution obtained before the tree search can replace this value immediately. The algorithm repeatedly selects an active node, analyzes its subproblem, and either closes it or creates children.
A typical node-processing sequence is:
- Apply inexpensive feasibility checks and tighten variable domains.
- Compute a valid lower bound on the node’s objective values.
- Discard the node if it is infeasible or its bound cannot improve .
- Use any feasible solution discovered during processing to update the incumbent.
- Close the node if its subproblem has been solved sufficiently to establish that no better solution remains there.
- Otherwise branch, preserving coverage of the unresolved possibilities, and place the children in the active collection.
There are three standard reasons for fathoming a node. Infeasibility means that its restricted problem has no feasible solutions. Bound dominance means that its lower bound is at least the incumbent value. Solution of the node means that its optimum has been established; for example, an optimal continuous relaxation solution may already satisfy all required integrality conditions.
Correctness follows from an invariant: every feasible solution that could improve the incumbent is either represented by an active or currently processed node, or has already been examined. Branching preserves this invariant through coverage. Infeasibility pruning removes no feasible solutions, and bound pruning removes no strictly improving solutions. Once the active collection is empty, no unexplored improving solution remains. This gives an optimality argument grounded in mathematical proof, not merely confidence obtained from unsuccessful searching.
The distinction between finding one optimum and enumerating all optima changes the pruning rule. If only one optimal solution is needed, suffices to prune. If every optimal solution must be recovered, nodes with may contain additional optima and generally cannot be removed on that basis alone.
Finite termination requires additional assumptions. A bounded problem with finitely many discrete assignments can be solved by a branching rule that eventually distinguishes every assignment, provided node operations terminate. Continuous problems require more care: subdivisions can continue indefinitely, and convergence may depend on shrinking regions and increasingly accurate bounds. Branch-and-bound also does not automatically resolve unboundedness. In particular, an unbounded relaxation of a mixed-integer problem is not, by itself, a proof that the original problem has feasible solutions with arbitrarily good objective values.
Relaxations and the construction of bounds
The most common way to obtain a bound is to solve a relaxation: a problem that is easier because some restrictions have been weakened or removed. If , then
The relaxed optimum is consequently a valid lower bound for minimization. The relaxation need not resemble the original problem computationally, provided the inequality is justified.
For mixed-integer linear optimization, the standard relaxation drops integrality and retains linear constraints. A problem of the form
becomes a linear programming problem when the designated integer variables are allowed to be real. Its optimal value bounds the mixed-integer optimum from below. If an optimal relaxation solution satisfies the integrality restrictions, it also solves the node’s original subproblem.
Bounds may instead come from Lagrangian duality, combinatorial arguments, or specialized optimization routines. A minimization problem with difficult constraints can use
For every feasible original solution, the added term is nonpositive, so is a lower bound. Choosing multipliers to maximize this bound can make it substantially stronger. In routing problems, lower-cost structures that omit some tour requirements can provide analogous bounds.
A useful distinction is between a feasible relaxation solution and a certified relaxation bound. For minimization, a feasible solution to the relaxed problem generally gives an upper bound on the relaxation optimum, not the lower bound needed for safe pruning of the original problem. A dual-feasible solution, by contrast, can provide a valid lower bound even before the relaxation is solved to optimality. Solver termination status therefore matters.
Stronger bounds are not always computationally preferable. A costly bound may remove many nodes but consume more time than exploring them with a cheaper bound. Implementations often apply a sequence of tests, beginning with simple arithmetic or domain checks and proceeding to expensive relaxations only when worthwhile.
Bounds can also be strengthened without re-solving a relaxation. A child inherits its parent’s valid lower bound. If all feasible objective values are integers, any finite real lower bound can be rounded upward to . More generally, known spacing between attainable objective values can support similar strengthening. Such deductions must follow from the actual objective structure; the mere presence of integer variables does not imply that objective values are integral.
Branching rules and node selection
Branching determines how uncertainty is resolved. In mixed-integer linear optimization, a common rule selects an integer-constrained variable whose relaxation value is fractional and creates two children:
These alternatives cover every integer value while excluding the current fractional value. If , the children impose and . Binary variables yield the familiar alternatives and .
The variable closest to a half-integer is sometimes selected because both branches remove a substantial portion of its local fractional interval. This “most fractional” rule is inexpensive but ignores objective information. Strong branching instead tentatively solves or partially solves candidate child relaxations and compares their predicted bound improvements. It can produce a much smaller tree, but testing many candidates is costly.
Pseudocost branching estimates the bound improvement per unit of variable movement from previous branching observations. Separate estimates are maintained for upward and downward branches. Reliability branching combines the approaches: strong branching supplies information when estimates are poorly supported, while pseudocosts are used once enough observations have accumulated. These rules illustrate that branching decisions exploit information gathered during the search, not just the current relaxation solution.
Node selection is a separate choice. Depth-first search follows one line of descent, often reaching complete feasible assignments quickly and requiring relatively little storage for the unresolved frontier. Best-bound search selects the active node with the smallest lower bound in minimization, directing effort toward the part of the tree currently limiting the global lower bound. Breadth-first search processes shallow levels first, but its frontier can become very large.
Neither rapid incumbent discovery nor rapid bound improvement is sufficient alone. An excellent incumbent makes more pruning possible, while stronger lower bounds establish its quality. Practical solvers therefore combine strategies, for example using depth-first dives to seek feasible solutions and best-bound processing to reduce the unresolved gap. Search order may change after a first incumbent is found or when memory becomes constrained.
Branching is not restricted to individual variables. A scheduling problem can branch on whether one task precedes another; a routing problem can require or forbid an edge; a set-partitioning model can branch on whether two items appear together. The important requirements are that the alternatives cover all relevant solutions, make progress, and preserve enough structure for the child bounds to remain tractable.
A worked integer-programming example
Consider the two-variable problem
The objective is to minimize the sum of two nonnegative integer variables while satisfying both inequalities. Dropping integrality produces a continuous linear program. Adding the two constraints gives
so every relaxation-feasible point has objective value at least .
The point satisfies both constraints with equality and attains that lower bound. The root relaxation therefore has optimum . It does not immediately provide an integer solution because both coordinates are fractional. Suppose a preliminary heuristic has found , giving incumbent value . The root bound is below 4, so it cannot yet be pruned by comparison with that incumbent.
Branching on creates the alternatives and . In the first child, the constraint implies
The point is feasible and has objective 3. It therefore solves this child’s relaxation and its integer problem simultaneously. The incumbent improves from 4 to 3, and the child can be closed.
For the second child, , the other original inequality gives
The point satisfies all constraints and achieves 3, so the second child also has relaxation optimum 3. Since the incumbent already has value 3, this child can be fathomed by its bound without seeking another solution. Both children are closed, proving that the original optimum is 3.
The example also shows how a stronger inference can eliminate the need for branching altogether. Because must be an integer, the root bound implies
If either or has already been found, the rounded lower bound equals the incumbent and proves optimality at the root.
Different output requirements lead to different processing. If the purpose is to find one optimum, the second child need not yield an explicit solution. If the purpose is to enumerate every optimum, the equality of its bound with 3 is not enough to discard it. The two points and both attain the minimum, and a procedure seeking all optima must retain the possibility of finding both.
Branch-and-cut, branch-and-price, and constraint inference
Modern mixed-integer solvers usually strengthen branch-and-bound with cutting planes. A cut is an inequality satisfied by every relevant integer-feasible solution but violated by some point of the current relaxation. Adding it removes fractional relaxation solutions without eliminating valid integer solutions. The combined framework is called branch-and-cut.
For a binary selection problem, suppose the total weight of a set of items exceeds the available capacity. Those items cannot all be chosen, so
is valid. Such a cover inequality can strengthen a knapsack problem relaxation. Other cut families exploit integrality, logical implications, or network structure. Their benefit is measured not just by immediate bound improvement but also by their effect on later node relaxations.
Cuts may be globally valid or locally valid. A global cut holds throughout the original feasible set and may be used across the tree. A local cut relies on restrictions imposed along a particular search path and is valid only within that node’s subtree. Incorrectly promoting a local inequality to global status can remove valid solutions. Cut management therefore includes validity scope as well as decisions about which inequalities to retain when the relaxation grows.
A different extension addresses formulations with too many variables to list explicitly. Column generation solves a restricted master problem and uses a pricing problem to identify omitted variables that could improve it. Combining this procedure with branching gives branch-and-price. Typical applications include vehicle routing and crew scheduling, where a variable can represent an entire feasible route or duty.
Bounding in branch-and-price requires care. For a minimization master problem, the optimum of a restricted set of columns is not automatically a lower bound on the optimum of the full linear relaxation. A valid node bound requires completion of pricing, or another rigorous argument accounting for omitted columns. Branching restrictions must also be translated into the pricing problems, which is why convenient branching rules may differ from ordinary variable branching.
Inference complements both approaches. Constraint programming reduces variable domains by propagating logical and numerical consequences. If a resource constraint is already saturated, for example, additional resource-consuming choices may be excluded immediately. Branch-and-bound can use such propagation before computing an optimization relaxation. Conversely, constraint-programming optimization can retain a best objective value and reject partial assignments that cannot beat it. The distinction lies mainly in how information is represented and propagated, rather than in an absolute separation between the methods.
Continuous and mixed-integer global optimization
Branch-and-bound also applies when the search space is continuous and the objective or constraints are nonconvex. A local optimization method may find a stationary point without establishing that it is globally best. In global optimization, branch-and-bound partitions the variable domain into regions, constructs valid lower bounds over those regions, and compares them with feasible objective values obtained by local search or other methods.
A common representation associates each node with a box
Branching splits one interval, often at its midpoint or at a selected relaxation value. The challenge is to build an underestimator that is valid throughout the box. Convex optimization can then provide bounds when a nonconvex problem is replaced by a suitable convex relaxation.
For a bilinear term , with and , the McCormick inequalities are
They describe the convex hull of the graph of a single bilinear term over its rectangular domain. When a model contains several interacting products, imposing these inequalities separately does not generally describe the convex hull of the entire feasible set.
Subdivision improves these relaxations because narrower variable intervals reduce the discrepancy between a nonlinear expression and its convex envelope or other underestimator. Bounds can also come from interval arithmetic, which encloses all possible values of an expression over a region. Straightforward interval evaluation may be weak because repeated appearances of the same variable are treated with insufficient dependence information; more sophisticated relaxations and domain reduction can improve the enclosure.
A continuous search need not terminate after finitely many subdivisions with an exact optimizer. Under appropriate compactness and consistency conditions, shrinking regions and convergent bounds can instead establish a solution within a prescribed absolute tolerance. An incumbent and valid global lower bound certify -optimality when . The conditions ensuring such convergence belong to the particular bounding and subdivision scheme, not to the name “branch-and-bound” alone.
Mixed-integer nonlinear programming combines discrete branching with this spatial subdivision. A solver may branch on integer variables to enforce integrality and on continuous variables to tighten nonlinear relaxations. If all nonlinearities are convex in the appropriate formulation, convex subproblems can supply global bounds; nonconvex models require additional global bounding machinery.
Numerical reliability, termination gaps, and implementation
The mathematical pruning rule assumes valid bounds and feasible incumbents. Computer implementations usually work with floating-point arithmetic, in which constraint residuals, objective values, and integrality checks are approximate. A value such as may be accepted as integral within a tolerance, but simply rounding a vector can violate coupled constraints. Feasibility checks and tolerances therefore form part of the practical interpretation of a solver’s result.
Numerical difficulties are particularly important when a bound is close to the incumbent. If a minimization lower bound is accidentally overestimated, an improving region may be pruned incorrectly. Poor scaling and nearly dependent constraints can worsen this risk. Large artificial constants in logical formulations can both weaken the relaxation and aggravate numerical behavior. These issues connect branch-and-bound to numerical stability and the conditioning of the underlying linear algebra.
Solvers commonly report an absolute optimality gap and a relative gap. One possible convention is
but definitions vary, particularly near zero or when bounds have different signs. A relative gap is meaningful only together with its stated denominator and termination rules. Stopping at a positive gap certifies an objective-value tolerance when the bounds are valid; it does not establish exact equality with the optimum.
Efficient node processing depends heavily on reusing information. Child relaxations often differ from their parents by only one or two variable bounds, so linear-programming bases or other warm-start data can substantially reduce reoptimization work. Nodes may store changes relative to ancestors rather than full copies of the model. Presolve can remove redundant restrictions, fix variables, or detect infeasibility before a large tree develops.
Parallel computing allows several nodes to be processed simultaneously. Workers share improved incumbents, selected cuts, and other information. Load balancing is difficult because superficially similar subtrees can require very different amounts of work. Search order also affects pruning: a worker that finds a strong incumbent early may eliminate work elsewhere, producing speedups greater than a simple division of a fixed workload. Other schedules can cause extra work by delaying that discovery.
More stringent certification can use rational reconstruction, exact arithmetic, or verified numerical enclosures. For suitable linear models, a certificate may include exact dual information for relaxation bounds and explicit evidence for each closed branch. Such certification is distinct from an ordinary floating-point solver log. The log records the computation’s progress, while an independently checkable certificate must support the mathematical validity of the exclusions on which the optimality claim depends.
Computational complexity and practical applications
Branch-and-bound is an exact framework, not a general polynomial-time solution to difficult optimization problems. With binary decisions, exhaustive branching can produce complete assignments and a binary tree of comparable exponential size. Good bounds can reduce this dramatically on particular instances, but weak relaxations may force the algorithm to explore much of the tree. Many important applications have NP-hardness, so no uniformly efficient behavior follows from using branch-and-bound.
Performance depends on the interaction between formulation and search. Two models can describe the same feasible decisions while giving very different continuous relaxations. A formulation whose relaxation closely approximates the convex hull of feasible integer points may require little branching. Another formulation with fewer variables but weak bounds can be much harder. Symmetry is a further obstacle: interchangeable machines, vehicles, or facilities can generate many distinct representations of essentially the same decision.
The traveling salesman problem illustrates the importance of relaxation structure. A degree-constrained relaxation may select several disconnected cycles rather than one tour. Connectivity inequalities rule out such subtours, strengthening the bound before or during branching. In vehicle routing, route-based formulations can be strong but enormous, motivating branch-and-price or branch-and-cut-and-price rather than a simple edge-variable tree.
Scheduling and resource-allocation applications use branches to decide assignments, start-time alternatives, or precedence relations. Bounds may ignore selected resource conflicts, relax integrality, or decompose the problem into simpler parts. Facility-location models choose which facilities to open and how to serve demand; production models combine continuous quantities with discrete setup decisions. In each case, the practical method is shaped by the model’s structure rather than by a universal branching recipe.
Branch-and-bound differs from dynamic programming in its principal means of reducing work. Dynamic programming merges repeated states or exploits a recurrence among subproblems. Branch-and-bound primarily rejects regions through objective bounds. The methods can nevertheless be combined: a dynamic program may solve a node relaxation, compute a combinatorial bound, or identify dominated partial decisions.
It also differs from a heuristic such as simulated annealing, which may discover a very good feasible solution without proving its quality. Heuristics are valuable inside branch-and-bound because every improved incumbent can strengthen pruning throughout the tree. A time-limited run may return a useful solution and a nonzero certified gap; whether the dominant achievement is solution discovery or proof of quality depends on the application and the state of the bounds.
Historical development
Branch-and-bound emerged from mid-twentieth-century operations research, when electronic computers made systematic discrete search increasingly practical but exhaustive enumeration remained prohibitively expensive. Its origins involve several related developments: methods for discrete programming, combinatorial routing algorithms, and more general formulations of bounded tree search. The framework grew through their interaction rather than through one immutable algorithm.
A foundational contribution was Ailsa H. Land and Alison G. Doig’s 1960 paper, An Automatic Method of Solving Discrete Programming Problems. Their method used linear-programming relaxations and systematic subdivision to address discrete optimization. It established an influential basis for what became mixed-integer branch-and-bound: continuous optimization supplied bounds, while additional restrictions progressively enforced the discrete requirements.
John D. C. Little, Katta G. Murty, Dura W. Sweeney, and Caroline Karel’s 1963 paper, An Algorithm for the Traveling Salesman Problem, was another landmark and helped establish the term “branch and bound.” Their method organized decisions about tour edges into a search tree and used reduced cost matrices to calculate bounds. It demonstrated how a problem-specific bounding procedure could turn a conceptually exhaustive search into a much more selective one.
Egon Balas’s 1965 additive algorithm provided an influential approach to zero-one integer programming through implicit enumeration and logical tests. Although its computational machinery differed from repeatedly solving linear programs, it belonged to the same broader effort to eliminate families of assignments without listing each member. These developments made clear that exact discrete optimization could draw on several kinds of bounding and inference.
Cutting-plane methods developed alongside tree search. Ralph Gomory’s work in the late 1950s supplied a general way to derive inequalities excluding fractional relaxation solutions while preserving integer solutions. Subsequent integration of cuts with branching led to branch-and-cut. Research on decomposition and column generation likewise supplied the foundations for branch-and-price, particularly for models whose natural variables represent complex combinatorial objects.
Later progress depended on improvements throughout the computational system: faster linear-programming methods, presolve, better branching decisions, primal heuristics, stronger cut generation, and more effective data structures. For nonlinear optimization, convex envelopes and spatial subdivision extended the same bounding principle beyond discrete domains. Contemporary research continues to investigate learned branching and node-selection policies, including methods using machine learning. Such policies can influence search efficiency, but the validity of an optimality result still rests on sound bounds, coverage-preserving branches, and justified pruning.