Branch-and-Cut
Branch-and-Cut is a widely used algorithmic framework for solving Mixed-Integer Linear Programming (MILP) problems. It extends the classical Branch-and-Bound method by dynamically strengthening relaxations through the addition of Cutting Planes. Today, Branch-and-Cut is the core solution approach implemented in most state-of-the-art MILP solvers.
Problem classes and applicability
Branch-and-Cut is primarily designed for Mixed-Integer Linear Programs (MILP), where the objective function and constraints are linear, and some variables are restricted to integer values. It is also applied to pure integer programs and certain combinatorial optimization problems.
The method relies on solving a sequence of Linear Programming (LP) relaxations, making it closely tied to LP solution techniques such as the Simplex method and Interior-Point methods. It can also be extended or combined with other frameworks, such as Branch-and-Price and Branch-Cut-and-Price, to handle large-scale or structured problems.
Core idea and algorithmic principle
Like Branch-and-Bound, Branch-and-Cut explores a search tree where each node corresponds to a subproblem with additional constraints. At each node, the integrality requirements are relaxed, producing a linear program that provides a bound on the optimal solution within that subproblem.
The key difference lies in the use of Cutting Planes. After solving the LP relaxation, the algorithm analyzes the fractional solution. If this solution violates known valid inequalities of the integer problem, additional linear constraints—called cuts—are generated and added to the relaxation. These cuts remove fractional solutions without excluding any feasible integer solutions.
This cutting process is repeated until no more violated cuts are found or a stopping criterion is reached. If the resulting solution is still fractional, the algorithm branches, creating new subproblems by splitting variable domains. Bounding and pruning proceed as in Branch-and-Bound.
Types of cuts and practical considerations
Common families of Cutting Planes include Gomory cuts, cover cuts, clique cuts, and flow cuts, among others. In practice, cuts are generated selectively to balance bound strength against computational cost.
Branch-and-Cut implementations often distinguish between global cuts, which apply to all nodes, and local cuts, which apply only within a subtree. Cuts may also be generated lazily, only when a candidate solution violates problem-specific constraints.
Role in modern optimization solvers
Branch-and-Cut provides a flexible and powerful framework for exact discrete optimization. By tightening relaxations dynamically, it significantly reduces the size of the search tree compared to pure Branch-and-Bound. Its modular structure allows seamless integration with heuristics, preprocessing, and advanced branching strategies, making it the dominant approach for large-scale MILP solving.
Further reading and references
Padberg, M., & Rinaldi, G. (1991). A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Review.
A seminal paper demonstrating the effectiveness of Branch-and-Cut on a large combinatorial problem.
Bertsimas, D., & Weismantel, R. (2005). Optimization over Integers. Dynamic Ideas.
A modern treatment of integer optimization algorithms, including Branch-and-Cut and related frameworks.
Achterberg, T. (2007). Constraint Integer Programming. PhD Thesis, ZIB.
A practical perspective on implementing Branch-and-Cut in modern solvers.