Does a cut always remove the current point strictly?

Not always. A neutral localization cut can pass through the query point while eliminating a halfspace.

Does one cut solve an integer problem?

Sometimes, as in the example, but many problems require more cuts, branching or other techniques.

Is a cut a heuristic guess?

A valid cutting-plane method needs inequalities justified for the relevant target set. Heuristic discovery does not remove the need to establish validity.

AI Glossary / Mathematics and optimization / Intermediate

Cutting-plane method

Definition

A cutting-plane method progressively narrows an optimization search by adding valid linear inequalities called cuts. Each cut excludes points that cannot belong to the relevant target set while retaining the solutions that matter. Cutting planes appear in both integer programming and continuous convex optimization, with different rules for constructing and interpreting the cuts.

What it means

A solver often begins with an easier or incomplete description of a problem. Its current candidate may violate an omitted requirement or fail to be optimal. A useful cut adds information that rules out an unhelpful region without losing a legitimate target solution.

In integer programming, cuts commonly strengthen a continuous relaxation while preserving all feasible integer points. In convex optimization, a separating inequality may preserve the minimizers while discarding feasible points known to be worse. These are related geometric ideas, but they do not preserve exactly the same set in every application.

How it works

Start with an initial relaxation or localization region containing the target set. Choose a candidate point by solving the current approximation or using a specified center-selection rule. A separation procedure, sometimes called an oracle, either accepts the point or supplies a valid cut.

Add the inequality and repeat. In a convex minimization problem, a subgradient g at x supplies the inequality gᵀ(z−x)≤0 for optimal points z, provided x is not already certified optimal. The justification comes from the global subgradient inequality, not just a local visual impression of the curve.

For integer models, arithmetic and combinatorial structure produce inequalities valid for integer solutions but violated by some fractional candidates. Practical algorithms may combine cuts with branching. Stopping requires an appropriate feasibility or optimality certificate, or a documented tolerance and bound gap, rather than simply accumulating many cuts.

Three practical examples

1. Integer allocation: eliminate fractional relaxation solutions that cannot represent valid whole-item decisions while preserving every valid integer plan.

2. Convex model fitting: build linear lower approximations or localization constraints from subgradients when the objective is nonsmooth but convex.

3. Large constraint systems: begin with a manageable subset and add violated valid constraints when a separation routine can identify them more efficiently than listing everything initially.

Think of it this way

Think of searching a map while receiving reliable statements that the destination lies on one side of a straight boundary. Each statement lets you cross out part of the remaining search area.

The crucial word is reliable. A guessed boundary can remove the destination and invalidate the search. Also, finding the next informative boundary may itself require substantial work; geometry does not make the oracle free.

Worked example

Consider an original integer problem: maximize x+y subject to 2x+2y≤5, with x and y nonnegative integers. Its continuous relaxation permits x+y=2.5, such as the fractional point (2.5,0), giving an upper bound of 2.5.

Because x+y is an integer, the original inequality implies x+y≤2. This is a valid cut: every feasible integer point satisfies it, while (2.5,0) does not. After adding the cut, the relaxation objective is at most 2. The feasible integer point (2,0) achieves 2, so the matching upper and lower bounds certify the optimum.

The cut does not make every point in the new relaxation integral. For example, (0.5,1.5) remains feasible. It nevertheless closes the objective gap for this particular problem.

For a separate convex illustration, minimize f(t)=(t−2)² on [0,6]. At t=4, the gradient is 4. The neutral cut 4(z−4)≤0 retains z≤4, including the true minimizer 2. It excludes some feasible but inferior points. This second cut preserves minimizers, whereas the integer cut preserves all feasible integer points. Both calculations are hand-checked, not solver traces.

Illustrative case study

Fictional case: a scheduling team tests a relaxation that repeatedly returns fractional staffing decisions. Analysts derive a valid inequality from the model's integer structure and verify it on small exhaustively checked instances before integrating it into the solver.

The inequality improves the relaxation bound but increases time spent solving each larger relaxation. The team evaluates total runtime and final gaps rather than celebrating the number of cuts generated. It keeps the original staffing rules available for independent validation of every proposed final schedule.

Common misconceptions and mistakes

Do not add a restriction merely because it removes the current candidate. It must preserve the appropriate target set.

Do not round arbitrary coefficients or right-hand sides and assume the result is valid. The worked integer example works because the entire left-hand expression is known to be integer.

Do not assume every tangent defines a valid global cut for a nonconvex function. Convexity or another justified structural argument is essential. Also distinguish cutting planes from branch-and-bound: cuts tighten regions, while branching creates subproblems. A combined branch-and-cut method uses both.

Business use

Cutting planes can make planning and analytical models tractable when useful constraints can be generated on demand. Their value depends on the strength and cost of the cuts, the quality of the relaxation and the solver's ability to manage an expanding system.

Require a clear validity argument and numerical handling of near-zero violations. Monitor bound improvement, solve time and memory. Redundant or weak cuts can create overhead without useful progress. If cuts are removed to control size, document the policy and ensure the remaining algorithm still has the claimed correctness and stopping properties.

Check your understanding

Why is x+y≤2 valid in the integer example but not an equivalent restriction for arbitrary real-valued x and y?

Answer: An integer sum cannot lie strictly between 2 and 2.5. Real-valued sums can, so the cut deliberately removes part of the continuous relaxation.

Related terms

Subgradient
Convex optimization
valid inequality
separation oracle
linear relaxation
integer programming
branch-and-cut
optimality gap

Learn next

derive a valid cut from another integer-valued linear expression and verify the preserved set. Then compare a neutral subgradient cut with a deeper cut that uses an additional objective bound.

Subgradient

Sources

Sources: Boyd and Vandenberghe, primary “Localization and Cutting-Plane Methods” notes, Sections 1–2 read: https://stanford.edu/class/ee364b/lectures/localization_methods_notes.pdf . MIT's “Applied Mathematical Programming,” Chapter 9, Section 9.8 on integer cuts consulted: https://web.mit.edu/15.053/www/AMP-Chapter-09.pdf . Integer and convex scopes are distinguished. Examples and fictional case are original; no benchmark is claimed.

Previous: Cutset conditioning Next: Cuzick - Edwards test