{ "id": "epd0saswwa", "slug": "cutting-plane-method", "title": "Cutting-plane method", "updated": "2026-10-21", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete" } ], "geo": [ { "id": "geo.nongeo.t1800.physical.math", "label": "Non-geographic · 1800 to 1945: Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.physical.math", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1800", "label": "Non-geographic · 1800 to 1945", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800" }, { "id": "geo.nongeo.t1800.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.physical" }, { "id": "geo.nongeo.t1800.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.physical.math" } ] }, { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Non-geographic · 1946 to 2000: Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" }, { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete" } ] } ], "excerpt": "The cutting-plane method is an optimization algorithm that solves a relaxed problem and adds linear constraints, called cuts, to remove parts of the relaxation containing no optimal solution of the original problem.", "snippet": "The cutting-plane method is an optimization algorithm that solves a relaxed problem and adds linear constraints, called cuts, to remove parts of the relaxation containing no optimal solution of the original problem.", "node": "physical.math.discrete", "markdown": "# Cutting-plane method\n\nA cutting-plane method is an optimization algorithm that solves a relaxed problem and adds linear constraints, called cuts, that remove parts of the relaxation containing no optimal solution of the original problem. It is used for integer and mixed-integer linear programming and for convex and quasiconvex optimization, including nonsmooth problems where gradients are replaced by subgradients or a separation oracle.[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf) • [2](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf) The method produced two lineages: in integer programming, [Ralph E. Gomory](https://www.edgepedia.org/ralph-e-gomory) gave a general cutting-plane algorithm in his 1958 paper *Outline of an algorithm for integer solutions to linear programs*;[3](https://doi.org/10.1090/s0002-9904-1958-10224-4) in convex optimization, a polyhedral-model variant is widely known as the Kelley method.[4](https://arxiv.org/pdf/1409.2636) Today cutting planes rarely run alone; they are a core component of branch-and-cut solvers and appear in machine learning applications such as regularized risk minimization, [multiple kernel learning](https://www.edgepedia.org/multiple-kernel-learning), and MAP inference.[2](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Output | A sequence of tightenings of a relaxation that raise the relaxation's bound while leaving the true integer optimum unchanged[5](https://arxiv.org/pdf/2406.18781) |\n| Main loop | Solve relaxation, separate a violated cut, add it, re-solve[6](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf) |\n| Origin (integer programming) | Gomory, *Outline of an algorithm for integer solutions to linear programs*, Bulletin of the American Mathematical Society, 1958[3](https://doi.org/10.1090/s0002-9904-1958-10224-4) |\n| Convex-side convergence | Kelley-method bound \\( f(\\bar{x}_{N}) - f^{\\ast} \\leq L \\cdot R/\\sqrt{N} \\) after \\( N \\) iterations, with subgradient bound \\( L \\) and domain diameter \\( R \\)[4](https://arxiv.org/pdf/1409.2636) |\n| Per-cut guarantee | Worst-case feasible-region volume reduction per iteration is at most a factor of 1 − 1/n in dimension n, rather than a fixed 50%[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf) • [19](https://web.stanford.edu/class/ee364b/lectures/localization_methods_slides.pdf) |\n| Solver impact | Disabling cutting planes degraded CPLEX overall performance[7](https://www.math.uwaterloo.ca/~rfukasaw/gomory.pdf) |\n| Dominant failure mode | Tailing off and numerical invalidity of cuts, so cuts are deployed inside branch-and-cut rather than as a standalone method[6](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf) • [8](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneDiscreta/MaterialeOD/2000%20-%20Mitchell%20-%20branch-and-cut.pdf) |\n\n## How it works\n\nThe method rests on a validity argument. For an integer program, the feasible integer points form a discrete set, and the convex hull of those points, the integer hull, is a polyhedron contained in the linear-programming relaxation. A valid cut is a linear inequality satisfied by every point of the integer hull; adding it shrinks the relaxation without removing any integer-feasible point, so the relaxed optimum can only move toward the true integer optimum.[6](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf) Gomory showed in 1958 that when the relaxation's optimal vertex \\( x^{\\ast} \\) is fractional, a cut separating \\( x^{\\ast} \\) from the integer hull can always be derived from a row of the optimal tableau by a rounding argument, so a separating cut exists whenever one is needed.[6](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf)\n\nIn the convex setting, the same geometry is applied to the level set of the objective: a cutting plane is a hyperplane separating the current point from the optimal points, and each cut tightens a polyhedral outer approximation of the feasible set.[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf) A cutting-plane proof formalizes the integer side: a target inequality is derived from the original constraints by a finite sequence of derived inequalities.[9](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/8fbabfd4ab31165cfc55f2baf5fff043_MIT15_083JF09_lec17.pdf)\n\n## How it is done\n\nThe practitioner loop has four steps, identical in structure on both lineages.[6](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf) • [10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf)\n\n1. **Relax and solve.** Solve the current relaxation, initially the LP relaxation with integrality ignored.[11](https://www.andrew.cmu.edu/user/gc0v/webpub/integerRioMPSjuly.pdf)\n2. **Check the incumbent.** If the optimal basic solution belongs to the integer feasible set (or, on the convex side, is feasible for the true set), stop; it is optimal.[10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf) • [12](https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/integer2.pdf)\n3. **Separate.** Otherwise solve a separation problem: find a violated valid inequality, such as \\( \\alpha \\cdot x + \\gamma \\cdot y \\leq \\beta \\), that cuts off the current solution.[10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf)\n4. **Add and re-solve.** Intersect the relaxation with the cut and repeat.[2](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf)\n\nTwo practical choices shape every implementation. There is a tradeoff between the running time of the separation procedure and the quality of the cuts it produces, and several cuts are often added per iteration.[10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf) Because the work per re-solve grows with the number of accumulated inequalities, implementations prune or drop old cuts as the algorithm progresses.[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf) On the convex side, iteration stops when the incumbent is feasible and \\( f_{0}(x^{(k)}) - l_{k} \\leq \\varepsilon \\), which guarantees \\( \\varepsilon \\)-suboptimality.[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf)\n\n## Origin\n\nThe integer-programming lineage begins with Ralph E. Gomory's 1958 paper in the *Bulletin of the American Mathematical Society*, which reduced integer linear programming to a sequence of linear programs.[3](https://doi.org/10.1090/s0002-9904-1958-10224-4) • [10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf) The theoretical impact was immediate, but when Gomory programmed the fractional cutting-plane algorithm later that year, convergence was often very slow, and he was disappointed by the computational results.[10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf) A mixed-integer extension followed that Gomory regarded as a straightforward extension of the original method and released as a Rand report rather than a journal paper.[13](https://www.cs.uleth.ca/~benkoczi/OR/read/gomory-cut-byGomory.pdf)\n\nFor more than three decades the cuts were deemed impractical. In 1996 Balas, Ceria, and Cornuéjols, with Natraj, obtained striking computational results using Gomory mixed-integer cuts and lift-and-project cuts within branch-and-bound.[12](https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/integer2.pdf) • [14](https://www2.isye.gatech.edu/~sdey30/ThCutSelection.pdf) By the late 1990s cutting planes had become a key component of commercial optimization solvers.[12](https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/integer2.pdf) The convex-optimization lineage developed separately, through the method now called the Kelley method and its bundle-method relatives.[4](https://arxiv.org/pdf/1409.2636) • [15](https://link.springer.com/content/pdf/10.1007/s10479-021-04498-y.pdf)\n\n## Variants\n\n**Integer-programming cuts.** Gomory's fractional cuts, the closely related Chvátal–Gomory cuts, and Gomory's mixed-integer cuts remain central to research.[7](https://www.math.uwaterloo.ca/~rfukasaw/gomory.pdf) MIR cuts, which perform nearly as well in solver tests, are another form of Gomory mixed-integer cuts.[16](https://www.maths.tcd.ie/EMIS/journals/DMJDMV/vol-ismp/37_cornuejols-gerard.pdf) The LP-relaxation framework gives a unified view of split cuts, Gomory mixed-integer cuts, intersection cuts, and, in the mixed 0–1 case, lift-and-project cuts.[11](https://www.andrew.cmu.edu/user/gc0v/webpub/integerRioMPSjuly.pdf) Structure-aware families include knapsack-based cuts, clique cuts, and flow covers; clique cuts are extremely useful for stable-set integer programs and flow covers for fixed-charge network-flow substructures.[8](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneDiscreta/MaterialeOD/2000%20-%20Mitchell%20-%20branch-and-cut.pdf) • [14](https://www2.isye.gatech.edu/~sdey30/ThCutSelection.pdf)\n\n**Convex-side variants.** These differ by the choice of query point where the next cut is taken: the center of gravity algorithm (method of central sections), the maximum volume ellipsoid (MVE) method, and the analytic center cutting-plane method (ACCPM).[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf) Bundle methods add a stabilization term to the cut-adding model to control iterate oscillation.[2](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf)\n\n## Applications\n\n**MILP solvers.** Cutting planes are a standard component of commercial solvers; CPLEX and XPRESS-MP incorporate cut generation into branch-and-bound, and the research packages MINTO and ABACUS implement branch-and-cut.[8](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneDiscreta/MaterialeOD/2000%20-%20Mitchell%20-%20branch-and-cut.pdf)\n\n**Combinatorial optimization.** The best-known branch-and-cut algorithms are those for the traveling salesman problem, which drove the 1980s revival through strong problem-specific cuts derived from polyhedral theory.[8](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneDiscreta/MaterialeOD/2000%20-%20Mitchell%20-%20branch-and-cut.pdf)\n\n**Machine learning.** Cutting-plane methods incrementally approximate a feasible set or objective by linear inequalities and have been applied to regularized risk minimization, multiple kernel learning, and MAP inference in graphical models.[2](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf)\n\n**A hard special-purpose success.** A hard integer program formulated by [Donald Knuth](https://www.edgepedia.org/donald-knuth) fifty years earlier was solved by three lexicographic cutting-plane algorithms using Gomory cuts, faster than CPLEX on that problem by a factor of at least 10.[17](https://dl.acm.org/doi/10.1007/s10107-011-0450-6)\n\n**Measuring progress.** In branch-and-cut, progress is measured by the integrality gap, \\( g_{k} := c^{\\top} \\cdot x_{\\mathrm{int}}^{\\ast} - c^{\\top} \\cdot x_{k}^{\\ast} \\geq 0 \\) at iteration \\( k \\), and by the integrality gap closure, the factor by which the gap is closed between the first relaxation and the current round.[5](https://arxiv.org/pdf/2406.18781)\n\n## Limitations and alternatives\n\n**Tailing off.** In branch-and-cut, the cutting loop eventually tails off, meaning successive relaxation solutions improve little; this is the standard signal to stop cutting and branch. Implementations often search for cuts only at every eighth node, with more rounds at the root, and the cut-and-branch variant adds cuts only at the root node.[8](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneDiscreta/MaterialeOD/2000%20-%20Mitchell%20-%20branch-and-cut.pdf)\n\n**Numerical fragility.** [Round-off error](https://www.edgepedia.org/round-off-error) can make a Gomory cut invalid, and an invalid cut may lead a solver to cut off the optimal solution and return an incorrect answer.[7](https://www.math.uwaterloo.ca/~rfukasaw/gomory.pdf) The textbook generating formula is not used directly in software; solvers add safeguards, yet practitioners still report the optimum being cut off occasionally.[16](https://www.maths.tcd.ie/EMIS/journals/DMJDMV/vol-ismp/37_cornuejols-gerard.pdf) Instability is worst over multiple rounds of cuts, so cuts with large dynamism, the ratio of the largest to smallest absolute coefficient, are discarded.[14](https://www2.isye.gatech.edu/~sdey30/ThCutSelection.pdf) • [10](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf) Reading both the vertex to cut and the cut from the same tableau creates a feedback that makes Kelley's method intrinsically nonrobust.[18](http://www.dei.unipd.it/~fisch/papers/slides/LaGromory.pdf)\n\n**Alternatives.** Pure cutting-plane algorithms do not work well in practice because cuts become increasingly parallel, accompanied by dual degeneracy and growing determinant size and condition number, so cuts are used in cut-and-branch or branch-and-cut mode.[6](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf) For problems to which interior-point methods apply, cutting-plane methods are usually less efficient, but they do not require differentiability and directly handle quasiconvex problems.[1](https://web.stanford.edu/class/ee392o/localization-methods.pdf) Alongside the subgradient method, the cutting-plane method was one of two seminal approaches to nondifferentiability, but the basic Kelley method performs poorly because subproblem solutions are unstable and iterates land far apart; bundle methods counter this with a stabilization term.[15](https://link.springer.com/content/pdf/10.1007/s10479-021-04498-y.pdf) • [4](https://arxiv.org/pdf/1409.2636) • [2](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf) Adding all possible Gomory cuts, up to \\( m \\) for an ILP with \\( m \\) constraints per round, would tighten the relaxation fastest but grows the constraint set exponentially, so methods select few cuts per iteration.[5](https://arxiv.org/pdf/2406.18781)\n\n## References\n\n1. [Localization and Cutting-plane Methods (Boyd & Vandenberghe course chapter)](https://web.stanford.edu/class/ee392o/localization-methods.pdf)\n2. [Cutting plane methods chapter, Optimization for Machine Learning (MIT Press, 2012)](https://cmp.felk.cvut.cz/~werner/papers/FraSonWer-CPA-MIT2012.pdf)\n3. [Ralph E. Gomory (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society.](https://doi.org/10.1090/s0002-9904-1958-10224-4)\n4. [On the Kelley method / An optimal variant of Kelley's cutting-plane method (arXiv 1409.2636)](https://arxiv.org/pdf/1409.2636)\n5. [Learning to Remove Cuts in Integer Linear Programming (arXiv 2406.18781)](https://arxiv.org/pdf/2406.18781)\n6. [Can pure cutting plane algorithms work?](https://math.uwaterloo.ca/~bico/bellairs/Gomory_cuts.pdf)\n7. [Gomory cuts chapter (Fukasawa et al., implementation and computational aspects)](https://www.math.uwaterloo.ca/~rfukasaw/gomory.pdf)\n8. [Branch-and-Cut Algorithms for Combinatorial Optimization Problems (J.E. Mitchell, Handbook chapter, 2000)](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneDiscreta/MaterialeOD/2000%20-%20Mitchell%20-%20branch-and-cut.pdf)\n9. [MIT 15.083 Lecture 17: Cutting plane methods I](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/8fbabfd4ab31165cfc55f2baf5fff043_MIT15_083JF09_lec17.pdf)\n10. [Conforti, Cornuéjols, Yıldız and Zambelli, Cutting plane algorithm (summer school notes)](https://eventos.cmm.uchile.cl/discretas2016/wp-content/uploads/sites/26/2015/12/ChileSummerSchool.pdf)\n11. [General-purpose cutting planes (Cornuéjols survey, CMU webpub)](https://www.andrew.cmu.edu/user/gc0v/webpub/integerRioMPSjuly.pdf)\n12. [Integer programming (part 2), Ryan Tibshirani lecture notes, CMU](https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/integer2.pdf)\n13. [Gomory's retrospective on the cutting-plane method ('...cut by Gomory')](https://www.cs.uleth.ca/~benkoczi/OR/read/gomory-cut-byGomory.pdf)\n14. [Theoretical challenges towards cutting-plane selection](https://www2.isye.gatech.edu/~sdey30/ThCutSelection.pdf)\n15. [Essentials of numerical nonsmooth optimization (4OR/Annals of Operations Research)](https://link.springer.com/content/pdf/10.1007/s10479-021-04498-y.pdf)\n16. [Gomory cuts (Cornuéjols, ISMP/DMV)](https://www.maths.tcd.ie/EMIS/journals/DMJDMV/vol-ismp/37_cornuejols-gerard.pdf)\n17. [A hard integer program made easy by lexicography (Mathematical Programming)](https://dl.acm.org/doi/10.1007/s10107-011-0450-6)\n18. [LaGromory slides (Fischetti/Lodi presentation)](http://www.dei.unipd.it/~fisch/papers/slides/LaGromory.pdf)\n19. [Localization Methods Slides.pdf, web.stanford.edu](https://web.stanford.edu/class/ee364b/lectures/localization_methods_slides.pdf)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026; Oct 21, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.stat.cmu.edu/~ryantibs/convexopt-F16/lectures/integer2.pdf", "https://www2.isye.gatech.edu/~sdey30/ThCutSelection.pdf" ], "url": "https://www.edgepedia.org/cutting-plane-method", "markdown_url": "https://www.edgepedia.org/cutting-plane-method.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Cutting-plane method\", Edgepedia (EdgeChat), https://www.edgepedia.org/cutting-plane-method. Edgepedia Community License 1.0.", "credit_md": "\"[Cutting-plane method](https://www.edgepedia.org/cutting-plane-method)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/cutting-plane-method](https://www.edgepedia.org/cutting-plane-method). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Cutting-plane method\", Edgepedia (EdgeChat), https://www.edgepedia.org/cutting-plane-method. Edgepedia Community License 1.0.", "speakable": "The cutting-plane method is an optimization algorithm that solves a relaxed problem and adds linear constraints, called cuts, to remove parts of the relaxation containing no optimal solution of the original problem." }