×

The Chvátal-Gomory closure of an ellipsoid is a polyhedron. (English) Zbl 1285.90081

Eisenbrand, Friedrich (ed.) et al., Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9–11, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13035-9/pbk). Lecture Notes in Computer Science 6080, 327-340 (2010).
Summary: It is well-know that the Chvátal-Gomory (CG) closure of a rational polyhedron is a rational polyhedron. In this paper, we show that the CG closure of a bounded full-dimensional ellipsoid, described by rational data, is a rational polytope. To the best of our knowledge, this is the first extension of the polyhedrality of the CG closure to a non-polyhedral set. A key feature of the proof is to verify that all non-integral points on the boundary of ellipsoids can be separated by some CG cut. Given a point \(u\) on the boundary of an ellipsoid that cannot be trivially separated using the CG cut parallel to its supporting hyperplane, the proof constructs a sequence of CG cuts that eventually separates \(u\). The polyhedrality of the CG closure is established using this separation result and a compactness argument. The proof also establishes some sufficient conditions for the polyhedrality result for general compact convex sets.
For the entire collection see [Zbl 1189.90006].

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization

Software:

FilMINT; Bonmin
PDFBibTeX XMLCite
Full Text: DOI