Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron
verfasst von : Santanu S. Dey, Juan Pablo Vielma
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.