Branch-and-Bound
Branch-and-Bound is a general algorithmic framework for solving optimization problems with discrete decision variables, most notably Mixed-Integer Linear Programming (MILP) and Mixed-Integer Nonlinear Programming (MINLP) problems. Rather than being a single algorithm, Branch-and-Bound defines a systematic approach to exploring a solution space while discarding large portions that cannot contain optimal solutions.
Problem classes and applicability
Branch-and-Bound is primarily used for problems involving integer or binary variables. It is the core solving paradigm behind most MILP solvers and also appears in nonlinear and combinatorial optimization contexts.
The framework relies on the ability to compute bounds on the best achievable objective value over subsets of the search space. These bounds are typically obtained by solving relaxations of the original problem, such as linear or convex relaxations.
Core idea and algorithmic principle
Branch-and-Bound organizes the solution process as a search tree. Each node in the tree corresponds to a subproblem defined by additional constraints, often fixing one or more variables to specific values or restricting their domains.
The algorithm proceeds in three main steps:
- Relaxation: Solve a relaxed version of the current subproblem by relaxing integrality or domain constraints. This produces a continuous optimization problem, often linear or convex, which is solved using standard continuous optimization algorithms such as Simplex, dual Simplex, or Interior-Point methods.
- Bounding: The optimal value of this relaxation serves as a bound on the best achievable objective within the subproblem.
- Branching: If the relaxation solution is infeasible for the original problem, the algorithm branches by adding mutually exclusive constraints that partition the feasible region. Most commonly, this involves splitting the domain of a fractional integer variable into disjoint subsets, thereby generating subproblems that together cover all feasible solutions.
Subproblems whose bounds are worse than the best known feasible solution are discarded. This pruning mechanism allows the algorithm to avoid exhaustive enumeration of all discrete combinations.
Search strategies and enhancements
The performance of Branch-and-Bound depends heavily on branching strategies, node selection policies, and the quality of bounds. Common enhancements include strong branching, pseudo-cost branching, and best-bound node selection.
In practice, Branch-and-Bound is rarely used alone. It forms the backbone of more advanced techniques such as Branch-and-Cut, Branch-and-Price, and Branch-Cut-and-Price, which incorporate cutting planes, column generation, or both. In nonlinear settings, spatial Branch-and-Bound extends the framework to handle nonconvex continuous variables.
Role in modern optimization solvers
Branch-and-Bound provides a unifying structure for exact discrete optimization. By combining relaxations, search, and pruning, it enables solvers to balance exploration and exploitation efficiently. Its flexibility allows it to integrate seamlessly with Linear Programming (LP), Nonlinear Programming (NLP), and constraint-based techniques.
Further reading and references
Land, A. H., & Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica.
The original paper introducing the Branch-and-Bound method for integer programming.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley.
A foundational textbook covering Branch-and-Bound theory, enhancements, and applications.
Bertsimas, D., & Weismantel, R. (2005). Optimization over Integers. Dynamic Ideas.
A modern reference with detailed analysis of integer optimization algorithms and Branch-and-Bound variants.