Abstract
In this paper, we show that the Chvátal-Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver [15] for irrational polytopes, and generalizes the same result for the case of rational polytopes [15], rational ellipsoids [7] and strictly convex bodies [6].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, Philadelphia, PA (2001)
Bonami, P., Dash, G.C.S., Fischetti, M., Lodi, A.: Projected Chvatal-Gomory Cuts for Mixed Integer Linear Programs. Mathematical Programming 113, 241–257 (2008)
Cassels, J.W.S.: An introduction to Diophantine approximation. Hafner, New York (1972)
Çezik, M.T., Iyengar, G.: Cuts for mixed 0-1 conic programming. Mathematical Programming 104, 179–202 (2005)
Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics 4, 305–337 (1973)
Dadush, D., Dey, S.S., Vielma, J.P.: The Chvátal-Gomory Closure of Strictly Convex Body (2010) (to appear in Mathematics of Operations Research)
Dey, S.S., Vielma, J.P.: The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 327–340. Springer, Heidelberg (2010)
Dunkel, J., Schulz, A.S.: The Gomory-chvátal closure of a non-rational polytope is a rational polytope (2010), http://www.optimization-online.org/DB_HTML/2010/11/2803.html
Edmonds, J.: Paths, trees, and flowers. Canadian Journal of mathematics 17, 449–467 (1965)
Fischetti, M., Lodi, A.: Optimizing over the first Chvátal closure. Mathematical Programming, Series B 110, 3–20 (2007)
Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64, 275–278 (1958)
Grötschel, M., Padberg, M.: On the symmetric travelling salesman problem I: Inequalities. Math. Programming 16, 265–280 (1979)
Grötschel, M., Padberg, M.: On the symmetric travelling salesman problem II: Lifting theorems and facets. Math. Programming 16, 281–302 (1979)
Niven, I.M.: Diophantine approximations. Interscience Publishers, New York (1963)
Schrijver, A.: On cutting planes. Annals of Discrete Mathematics 9, 291–296 (1980); combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part II
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dadush, D., Dey, S.S., Vielma, J.P. (2011). On the Chvátal-Gomory Closure of a Compact Convex Set. In: Günlük, O., Woeginger, G.J. (eds) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, vol 6655. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20807-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-20807-2_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20806-5
Online ISBN: 978-3-642-20807-2
eBook Packages: Computer ScienceComputer Science (R0)