On the Chvtal-Gomory Closure of a Compact Convex Set

Daniel Dadush(dndadushgatech.edu)
Santanu S. Dey(santanu.deyisye.gatech.edu)
Juan Pablo Vielma(jvielmapitt.edu)

Abstract: In this paper, we show that the Chatal-Gomory closure of a compact convex set is a rational polytope. This resolves an open question discussed in Schrijver 1980 and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex sets (Dadush et. al 2010). In particular, it shows that the CG closure of an irrational polytope is a rational polytope, which was the open question in Schrijver 1980.

Keywords: CG closure, nonlinear integer programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation:

Download: [PDF]

Entry Submitted: 11/07/2010
Entry Accepted: 11/08/2010
Entry Last Modified: 11/07/2010

Modify/Update this entry