Solving a Mixed-Integer Programme (MIP) exactly requires searching over integer combinations. The standard starting point is the LP relaxation: drop the integrality constraints, solve a cheap continuous problem, and use the result as a lower bound. The trouble is that the LP solution is almost always fractional — it lives at a corner of the LP polytope that no integer solution occupies.
One option is to branch (split on a fractional variable), but large models can require millions of branch-and-bound nodes before an integer solution is proven optimal. Cutting planes offer an alternative: add a new linear constraint that is valid (no integer solution violates it), but that cuts off the current fractional LP corner. After adding the cut, re-solve the LP — the new solution is closer to the integer hull, and the bound tightens, often eliminating entire subtrees from the search.
Picture a two-variable MIP where x₁ and x₂ must be non-negative integers. The LP relaxation describes a convex polytope — a polygon in continuous space. The integer hull is the convex hull of all integer-feasible points inside that polygon. Every vertex of the integer hull satisfies a set of valid inequalities that the fractional LP vertices do not.
A cutting plane is one such inequality. Geometrically, it is a hyperplane that:
· passes between the current fractional LP solution and the integer hull, and
· does not cut off any integer-feasible point.
Adding cuts one-by-one shrinks the LP polytope until it (ideally) converges to the integer hull. In practice, a small number of well-chosen cuts can close 80–90% of the integrality gap, turning a problem that would need millions of branch-and-bound nodes into one that solves at the root.
Problem: A grid operator must decide which generators to switch on (binary: on/off) and how much power each produces (continuous: MW output) for each half-hour slot over 48 hours. This is a Mixed-Integer Programme (MIP) with hundreds of binary start/stop decisions and thousands of continuous dispatch variables.
LP relaxation corner: The solver first solves the LP relaxation and finds a corner solution where generator G3 is "0.6 on" — partially committed. This is physically meaningless but gives a tight lower bound on cost.
Adding a cut: The solver adds a minimum-up-time cut: "if G3 starts in period t, it must remain on for at least 4 consecutive periods." This valid inequality is implied by the integer constraints but not by the LP polytope. The fractional corner violating this cut is removed from the search space.
Result: After a handful of such cuts, the LP bound jumps close to the integer optimum. The branch-and-cut tree shrinks from potentially millions of nodes to a few thousand — and the AFRY BID3 system, which deploys this approach using FICO Xpress, schedules the Great Britain grid in seconds rather than hours.
Common confusion: A cut is called "cutting off" the LP solution, so surely it cuts off some integer solutions too?
Reality: This is the defining property that makes a cut valid: it must be satisfied by every integer-feasible solution. The geometric picture helps — the cut hyperplane lies strictly between the fractional LP corner and any integer point. No integer solution is on the wrong side of a valid cut. If a proposed inequality ever excluded an integer solution, it would not be a cutting plane — it would be an error.
Common confusion: Tighter bounds are better, so add as many cuts as possible.
Reality: Each cut adds a row to the LP, making each LP solve slower. Weak cuts that barely move the bound cost more in LP time than they save in branching. Modern solvers (Gurobi, FICO Xpress, HiGHS) use sophisticated cut selection — they generate many candidate cuts from different families (Gomory–Chvátal cuts, Mixed-Integer Rounding (MIR) cuts, knapsack cover cuts) and apply only those that tighten the bound significantly. Indiscriminate cut generation is a known performance anti-pattern.
Common confusion: Cuts are a theoretical tool used in research; production solvers just branch.
Reality: Every major commercial solver — FICO Xpress, Gurobi, CPLEX, HiGHS — runs an aggressive cut-generation phase at every node of the branch-and-bound tree (hence the name branch-and-cut). Industrial cases like power-grid unit commitment (AFRY BID3), airline crew scheduling, and retail lending optimisation (Erste Group) all rely heavily on cuts to be tractable at commercial scale. Turning off cuts in Gurobi, for example, typically makes hard MIPs orders of magnitude slower.
Origin: Ralph Gomory (1958) showed that for any LP solution with a fractional variable x_j = f + integer part, a valid cut can be derived by taking a linear combination of the LP rows and rounding down. Václav Chvátal (1973) generalised this to a systematic procedure for deriving all cuts implied by any LP over integers.
What a Gomory–Chvátal cut looks like: Given the LP optimal tableau row for variable x_j: x_j + Σ ā_{jk} x_k = b̄_j where b̄_j is fractional, the Gomory cut is: Σ frac(ā_{jk}) x_k ≥ frac(b̄_j). This cuts off the current LP vertex but keeps all integer solutions on the correct side.
Practical descendants: Mixed-Integer Rounding (MIR) cuts, split cuts, lift-and-project cuts, and knapsack cover cuts are all generalisations or specialisations of the Gomory–Chvátal framework. Modern solvers generate cuts from multiple families simultaneously, choosing those with the best "efficacy" (how far the LP optimum is pushed) relative to their LP cost.
A cutting plane slices off the fractional LP corner without removing any integer solution — each cut is free information that tightens the bound and shrinks the branch-and-bound tree.