A cutting-plane method is a family of algorithms in mathematical optimization that progressively refine an approximation to a problem by adding linear inequalities called cuts. Each cut excludes part of the current approximation without excluding any solution that must be retained. In integer programming, cuts typically remove fractional solutions of a continuous relaxation while preserving all feasible integer solutions. In convex optimization, they can separate infeasible points from the feasible region or provide affine lower bounds on the objective function.
The term denotes an algorithmic framework rather than a single algorithm. Its effectiveness depends on how cuts are generated, how the next candidate solution is chosen, and how the accumulated inequalities are managed.
Geometric principle
A linear inequality
defines a half-space, bounded by the hyperplane . Suppose the original feasible set is , while a simpler set contains it:
If a candidate point is not acceptable, a cutting-plane algorithm seeks an inequality satisfying
The next approximation is
Thus the cut preserves but removes the current candidate.
When cuts are retained, the approximations are nested:
If the approximations are defined by finitely many linear inequalities, they are polyhedra.
A fundamental distinction is between a valid inequality, which holds throughout the target set, and a separating cut, which also excludes the point currently under consideration. A valid inequality already satisfied by that point may be useful later but does not separate it now.
General algorithm
A typical optimization-based cutting-plane procedure has the following structure:
- Construct a relaxation. Replace the original problem with a simpler problem whose feasible region contains the original feasible set.
- Solve the current relaxation. Obtain a candidate solution and a bound on the original optimal value.
- Test the candidate. Determine whether it satisfies the omitted requirements or whether the current approximation is sufficiently accurate.
- Generate cuts. Add one or more inequalities violated by the candidate.
- Repeat. Stop when optimality, infeasibility, or a prescribed accuracy has been established.
The current relaxation is often called the master problem. It is frequently a linear program, although quadratic, conic, and other master problems also occur.
For a minimization problem, a valid relaxation provides a lower bound on the optimal value. Any feasible solution provides an upper bound. Their difference supplies a stopping criterion. For maximization, the roles of the bounds are reversed.
Not every cutting-plane algorithm chooses its next point by optimizing a master problem. Localization methods instead select a representative point from a region known to contain a solution, then shrink that region using new information.
Cutting planes for integer programming
Consider the integer linear program
Its linear programming relaxation replaces with . The relaxed problem is generally easier to solve, but its optimum may be fractional.
Let
Every linear inequality valid for is also valid for its convex hull, . Consequently, integer-programming cuts can be understood as improving an approximation to the integer hull.
If the relaxation exactly describes the integer hull and a finite optimum is attained, it has an integer optimal solution. Explicitly describing that hull, however, may require an enormous number of inequalities. Cutting-plane methods generate selected inequalities as needed rather than constructing the entire description in advance.
A simple example
Consider
The continuous relaxation has optimal value . Dividing its constraint by two gives
Because the left-hand side is an integer at every integer-feasible point, this inequality can be strengthened to
The strengthened inequality cuts off all relaxation optima with objective value , while retaining every feasible integer point. The integer optimum is therefore .
The strengthening is not valid for the original continuous region: its justification depends on integrality.
Chvátal–Gomory cuts
A Chvátal–Gomory cut generalizes this rounding argument. For a pure integer system , take nonnegative multipliers such that has integer coefficients. Every feasible integer point then satisfies
The nonnegative combination preserves validity, and rounding down the right-hand side is justified because the left-hand side is integer-valued.
Repeated rounds of such cuts can progressively strengthen a relaxation. For rational polyhedra, finitely many rounds suffice in principle to obtain the integer hull. A round conceptually applies all cuts of the relevant type, however; this result is not a guarantee that an arbitrary strategy adding individual cuts will terminate quickly.
Gomory fractional cuts
A classical Gomory fractional cut is derived from a row of a simplex tableau for a pure integer problem. Suppose the row is
where all displayed variables are constrained to be nonnegative integers. Write
If is fractional, the associated cut is
At the current basic solution, the nonbasic variables are zero, so the inequality is violated. Its validity follows from the tableau equation and the variables’ integrality.
This formula does not apply unchanged when some variables are continuous. Mixed-integer problems require cuts that account for which variables must be integral.
Cutting planes for convex optimization
Cutting-plane methods also exploit the supporting geometry of convex functions.
For a convex function , a subgradient at satisfies
throughout its domain. If is differentiable, its gradient is a subgradient.
This inequality gives a global affine lower bound. Accumulating such bounds produces the piecewise-linear model
with .
Kelley’s cutting-plane method
For
where is a convex set, Kelley’s method chooses a new candidate by solving
When is polyhedral, this is a linear program. An appropriate initial domain or other bounding structure is needed to keep the master problem well posed.
The master optimum supplies a lower bound on the true minimum. The best evaluated feasible objective value supplies an upper bound. Their gap can certify approximate optimality.
Although the cuts are lower bounds on the function, they are outer approximations to its epigraph: the set of pairs satisfying .
Cuts for convex constraints
Suppose a constraint is
with convex. If and is a subgradient at , every feasible point satisfies
This inequality excludes the current infeasible point while preserving the constraint’s feasible region.
Convexity is essential to this justification. A tangent approximation to a nonconvex function need not be a global lower bound and may incorrectly exclude feasible or optimal solutions.
Separation and computational complexity
A separation oracle takes a candidate point and either confirms membership in a target convex set or returns a separating inequality. This allows a cutting-plane algorithm to work with a set whose constraints are too numerous to list explicitly.
For example, some formulations of the traveling salesman problem contain exponentially many subtour-elimination inequalities. A solver can begin with only some of them and search for violated inequalities as solutions are generated.
The ellipsoid method established an important connection between separation and optimization. Under suitable encoding, boundedness, and precision assumptions, efficient separation can be used to obtain efficient optimization over convex sets. The associated polynomial-time results do not imply that every practical cutting-plane implementation is polynomial-time, or that separation is easy for every useful family of cuts.
Finding a strong violated inequality can itself be a difficult optimization problem. Practical algorithms therefore often combine exact separation procedures with heuristic searches.
Related methods and practical variants
Branch-and-cut
Modern mixed-integer solvers commonly combine cutting planes with branch-and-bound, producing branch-and-cut algorithms.
Cuts strengthen relaxations and improve bounds; branching divides the search into subproblems. These mechanisms complement one another: cuts may eliminate the need for substantial branching, while branching can make progress when cut generation stalls.
A global cut is valid throughout the original feasible set. A local cut may depend on restrictions imposed at one search-tree node and is valid only within the corresponding subtree. Confusing these validity scopes can invalidate the optimization result.
Benders decomposition
Benders decomposition separates a problem into a master problem and subproblems. Under the relevant linear or convex assumptions, subproblem information generates feasibility cuts or optimality cuts in the master-variable space.
This approach is useful when fixing one group of variables makes the remaining optimization substantially easier, including many planning and scenario-based models.
Stabilized and bundle methods
Unstabilized convex cutting-plane methods can move between distant points where the accumulated lower model is overly optimistic. Bundle methods retain subgradient information but add stabilization, often through a proximal term or a trust region.
Such methods preserve the central idea of building a model from supporting inequalities while controlling the choice of new evaluation points.
History
Cutting-plane ideas developed along several related paths. Work by George Dantzig, Ray Fulkerson, and Selmer Johnson on the traveling salesman problem in the 1950s demonstrated the use of problem-specific inequalities to strengthen linear programming formulations.
Ralph Gomory introduced a general cutting-plane procedure for integer programming in 1958. J. E. Kelley Jr.’s 1960 method applied successive supporting hyperplanes to convex optimization. Jacques Benders’s 1962 decomposition method provided another influential framework for generating cuts from subproblems.
Later developments combined general-purpose cuts, problem-specific separation, decomposition, and search. This combination became central to large-scale mixed-integer optimization.
Limitations and implementation issues
Cut validity alone does not ensure computational usefulness. Important considerations include:
- Strength. A cut may exclude the current point but improve the objective bound only slightly.
- Generation cost. Searching for a strong cut may cost more than the subsequent improvement saves.
- Master-problem growth. Accumulating many inequalities increases memory use and solution time.
- Redundancy. Similar cuts can add substantial computational work with little additional tightening.
- Numerical conditioning. Large or poorly scaled coefficients can cause problems for floating-point arithmetic.
- Convergence assumptions. Finite termination or convergence depends on the problem class, selection rules, arithmetic model, and other algorithmic details.
Implementations therefore select, scale, age, and sometimes delete cuts. If cuts are removed, successive relaxations need not remain nested, and their bounds need not improve monotonically unless earlier valid bounds are retained separately.
Theoretical finite-convergence results for particular exact-arithmetic procedures should also be distinguished from practical behavior under numerical tolerances. A point can appear feasible within a solver’s tolerance while violating a mathematical inequality by a small amount. Reliable implementations must handle these tolerances without treating an invalid inequality as a legitimate cut.