The triangle closure is a polyhedron
From MaRDI portal
Publication:2248744
Abstract: Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel [ An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res. 35 (2010), 233--256] and Averkov [On finitely generated closures in the theory of cutting planes, Discrete Optimization 9 (2012), no. 4, 209--215], some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. In this paper, we show that when the number of integer variables the triangle closure is indeed a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of this proof are also used to give a refinement of necessary conditions for valid inequalities being facet-defining due to Cornu'ejols and Margot [On the facets of mixed integer programs with two integer variables and two constraints, Mathematical Programming 120 (2009), 429--456] and obtain polynomial complexity results about the mixed integer hull.
Recommendations
Cites work
- An analysis of mixed integer linear sets based on lattice point free convex sets
- Chvátal closures for mixed integer programming problems
- Convex Analysis
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Maximal lattice-free convex sets in linear subspaces
- Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
- Minimal valid inequalities for integer constraints
- On degenerate multi-row Gomory cuts
- On finitely generated closures in the theory of cutting planes
- On integer points in polyhedra
- On the continuity of the maximum in parametric linear programming
- On the facets of mixed integer programs with two integer variables and two constraints
- On the relative strength of split, triangle and quadrilateral cuts
- Split rank of triangle and quadrilateral inequalities
- Two row mixed-integer cuts via lifting
Cited in
(11)- On finitely generated closures in the theory of cutting planes
- The aggregation closure is polyhedral for packing and covering integer programs
- On a generalization of the Chvátal-Gomory closure
- Constructing lattice-free gradient polyhedra in dimension two
- Lattice closures of polyhedra
- An analysis of mixed integer linear sets based on lattice point free convex sets
- On the polyhedrality of cross and quadrilateral closures
- The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron
- On the polyhedrality of closures of multibranch split sets and other polyhedra with bounded max-facet-width
- Constructing lattice-free gradient polyhedra in dimension two
- Split cuts in the plane
This page was built for publication: The triangle closure is a polyhedron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248744)
