TL;DR
This paper proves that the Chvátal-Gomory (CG) closure of any compact convex set is a rational polytope. This resolves a long-standing open question in combinatorial optimization and generalizes previous results, showing that even irrational polytopes can be "rationalized" through this closure process.
What Problem Does This Paper Address?
The Chvátal-Gomory closure is a fundamental concept in integer programming, representing the set obtained by iteratively adding cutting planes (CG cuts) derived from the set's support function. For rational polyhedra, it's known that the CG closure is also a rational polyhedron. However, a key open question, highlighted by Schrijver, was whether this property holds for general convex sets, particularly for irrational polytopes. The challenge lies in handling irrationality, which breaks down the standard assumptions about rational data and extreme points. This paper directly addresses this by proving the CG closure of any compact convex set is a rational polytope.
Methods
The authors employ a sophisticated proof strategy that builds upon existing techniques for rational polyhedra and strictly convex sets, but introduces novel elements to handle irrationality. Key aspects include:
- Lifting CG Cuts: A crucial technique involves "lifting" CG cuts defined for faces of the convex set to become valid CG cuts for the entire set. This is achieved through a generalized version of the "lifting approach" and relies on Dirichlet's approximation theorem.
- Approximation Arguments: The proof constructs approximations of the CG closure. First, an approximation is built that is a polytope and contained within the set's affine hull. A second approximation refines this by ensuring its intersection with the relative boundary of the set matches that of the true CG closure.
- Induction on Dimension: The main result is proven by induction on the dimension of the convex set. The base case (zero-dimensional set) is trivial, and the inductive step leverages the properties of proper exposed faces and the previously constructed approximations.
- Unimodular Transformations: Lemma 3.5 and its subsequent use are critical for transforming irrational vectors into a structured form that simplifies the analysis of CG cuts.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Irrationality is Not a Barrier: The most significant insight is that even when dealing with irrational data or structures, the CG closure process can still yield a rational polytope. This is a powerful result for understanding the structure of feasible regions in integer programming.
- Generalization of CG Closure Properties: The paper extends known results about CG closures from rational polyhedra and strictly convex sets to the broader class of compact convex sets.
- The Role of Affine Hulls: The concept of
aff₁(A)(the largest integer subspace within the affine hull of A) plays a crucial role in constructing approximations and handling irrationality. - Structure of CG Closures: The proof reveals that the CG closure of a compact convex set is not only rational but also a polytope, meaning it can be described by a finite set of inequalities.
Key Results
- Main Theorem: The Chvátal-Gomory closure of any non-empty compact convex set $K \subseteq \mathbb{R}^n$ is a rational polytope. This means there exists a finite set of CG cuts that define the closure.
- Resolution of Open Question: The paper resolves the open question posed by Schrijver regarding the CG closure of irrational polytopes.
- Technical Lemmas and Propositions: Several technical results are proven, such as Proposition 3.1 (lifting CG cuts for faces to the whole set) and Proposition 4.2 (constructing an approximation that matches the boundary intersection), which are essential building blocks for the main theorem.
Limitations and Future Work
The paper focuses on compact convex sets. The authors note in footnote 2 that if the convex hull of integer points is not a polyhedron, the CG closure might not be a rational polyhedron. This suggests that extending the results to non-compact sets or sets not defined by polyhedral structures might require different approaches. The paper also mentions that the proof idea is similar to that used for strictly convex sets, hinting at potential connections and further research directions in comparing these different classes of convex sets.
Summary updated