Name
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 et al. (Math Oper Res 35(1):233---256, 2010 ) and Averkov (Discret Optimiz 9(4):209---215, 2012 ), 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 $$m=2$$ 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éjols and Margot (Math Program 120:429---456, 2009 ) and obtain polynomial complexity results about the mixed integer hull. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10107-013-0639-y | Mathematical Programming: Series A and B |
Keywords | DocType | Volume |
cutting planes,polyhedral closures,integer programming,90c10,90c11,lattice points,convex set,cutting plane,discrete mathematics | Journal | 145 |
Issue | ISSN | Citations |
1-2 | 1436-4646 | 5 |
PageRank | References | Authors |
0.44 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amitabh Basu | 1 | 331 | 27.36 |
| Robert Hildebrand | 2 | 69 | 7.82 |
| Matthias KöPpe | 3 | 191 | 20.95 |