Cutting Planes
Cutting Planes are a class of techniques used to strengthen mathematical optimization formulations by iteratively refining feasible regions. They play a central role in integer programming, particularly in Mixed-Integer Linear Programming (MILP), and are a key component of modern exact solvers. Rather than enumerating discrete solutions directly, Cutting Planes improve the quality of continuous relaxations used within broader algorithmic frameworks.
Problem classes and applicability
Cutting Planes are primarily associated with Integer and Mixed-Integer Linear Programs (MILP), but similar ideas also appear in Nonlinear Programming (NLP) and convex optimization. They are most effective when an optimization problem admits a strong linear relaxation that can be systematically tightened.
In practice, Cutting Planes are rarely used as standalone algorithms. Instead, they are embedded within methods such as Branch-and-Cut, Branch-Cut-and-Price, and cutting-plane-based decomposition methods. They are also closely related to polyhedral optimization, which aims to describe the convex hull of feasible integer solutions.
Core idea and algorithmic principle
The fundamental idea of Cutting Planes is to iteratively add valid constraints to an optimization problem in order to eliminate infeasible or undesirable solutions. Typically, the process begins by solving a relaxed problem, often a linear programming relaxation that ignores integrality constraints.
If the solution of this relaxation violates integrality or other structural requirements, the algorithm identifies a valid inequality, or cut, that is satisfied by all feasible integer solutions but violated by the current fractional solution. This cut is then added to the model, shrinking the feasible region of the relaxation.
The strengthened relaxation is solved again, and the process repeats until no further violated cuts can be found or an integer-feasible solution is obtained. This iterative refinement improves the bounds used in search-based methods and reduces the need for branching.
Types of cutting planes
A wide variety of cutting planes have been developed, each exploiting specific mathematical structures present in integer and mixed-integer optimization problems.
- Gomory cuts are general-purpose Cutting Planes derived from the solution of a linear programming relaxation. When the relaxation produces a fractional value for a variable that must be integer, a Gomory cut is constructed directly from the corresponding simplex tableau row. The cut excludes the current fractional solution while remaining valid for all integer-feasible solutions. Gomory cuts do not rely on problem-specific structure and can, in principle, be generated for any integer program, although in practice they are often used selectively due to numerical and performance considerations.
- Cover cuts arise from knapsack constraints of the form
If a subset of variables C satisfies \sum_{i \in C} a_i > b, then at most |C| - 1 variables in C can be equal to 1. This leads to the valid inequality
\sum_{i \in C} x_i \leq |C| - 1which cuts off fractional solutions that violate this combinatorial structure.
- Clique cuts exploit mutual exclusivity relationships between binary variables. If a set of variables represents choices that cannot be simultaneously selected, a clique cut enforces
where K is a clique in a conflict graph. These cuts are common in scheduling, routing, and assignment problems.
- Flow cuts leverage the structure of network flow constraints, such as capacity limitations or conservation laws. They are frequently used in transportation and logistics models to tighten relaxations by enforcing flow feasibility conditions.
In practice, solvers use a combination of general-purpose cuts and problem-specific cuts. Cut generation is often selective, as excessive cutting can increase computational overhead without improving performance.
Role in Modern Optimization Solvers
Cutting planes are a foundational element of modern MILP solvers. They significantly enhance the effectiveness of Branch-and-Bound by tightening relaxations early in the search. Combined with heuristics and advanced branching strategies, cutting planes help make large-scale discrete optimization tractable.
Further Reading and References
Gomory, R. E. (1958). Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society.
The original paper introducing Gomory’s Cutting Plane method.
Chvátal, V. (1973). Edmonds Polytopes and a Hierarchy of Combinatorial Problems. Discrete Mathematics.
A foundational work connecting Cutting Planes to polyhedral combinatorics.
Cornuéjols, G. (2008). Valid Inequalities for Mixed Integer Linear Programs. Mathematical Programming.
A modern survey of Cutting Plane techniques used in MILP solvers.