Characterization of the split closure via geometric lifting

Amitabh Basu, Marco Molinaro

Introduction

In Mixed-Integer Programming (MIP), the efficiency of solvers depends heavily on the quality of "cutting planes"—linear inequalities that tighten the continuous relaxation of a problem by removing non-integer solutions. Historically, research into cutting planes has diverged into two distinct methodologies: Cut-Generating Functions (CGFs) and Disjunctive Programming. CGFs, such as the Gomory Mixed-Integer (GMI) cut, offer rapid, formula-based generation. In contrast, disjunctive cuts, like split cuts, are derived from logical "either-or" conditions; while often more powerful, they typically require solving auxiliary optimization problems.

This paper bridges the gap between these paradigms. By introducing a new family of inequalities termed $\alpha$-cuts, the authors demonstrate that these formula-based cuts are mathematically equivalent to the entire split closure of corner relaxations. Furthermore, the study utilizes this framework to explore the theoretical limits of split cuts, specifically addressing the integrality gaps in pure-integer programs.

Methodology: Geometric Lifting and $\alpha$-cuts

The authors utilize a technique known as geometric lifting to analyze the relationship between different cut families. This approach involves lifting a lower-dimensional optimization problem into a higher-dimensional space where the geometry—often characterized by lattice-free sets—is more manageable. The resulting inequalities are then projected back into the original space.

The Corner Relaxation

The analysis focuses on the corner relaxation, a simplified model of an integer program that isolates the essential difficulty of the problem. By studying the corner relaxation, the authors can derive deep mathematical properties that remain applicable to more complex, general MIPs.

Defining $\alpha$-cuts

A central contribution of this work is the definition of $\alpha$-cuts. These are a generalization of $k$-cuts, constructed by taking an integer combination of rows (represented by the vector $\alpha$) and applying the GMI function. Unlike standard Mixed-Integer Rounding (MIR) functions that may rely on rational parameters, $\alpha$-cuts are parameterized strictly by integers. This significantly simplifies the search space for identifying effective cuts.

Key Insights

The Universality of the Infinite-Dimensional Model

The paper establishes that the "infinite-dimensional" corner relaxation serves as a universal parent model. The authors prove that any split cut for a specific, finite-dimensional problem is essentially a "slice" or restriction of a cut derived from this infinite-dimensional model. This provides a unified theoretical foundation for understanding split cuts across various problem dimensions.

Integrality Gaps in Pure-Integer Programs

A significant finding concerns the strength of split cuts. While it was well-documented that mixed-integer programs could exhibit weak split closures, there was a prevailing intuition that pure-integer programs (where all variables are constrained to be integers) might be better behaved. The authors provide a rigorous counter-example to this intuition. They demonstrate that even in pure-integer cases, the gap between the split closure and the true integer hull can be arbitrarily large.

Main Results

The theoretical findings are summarized in three primary theorems:

  1. Theorem 1 (Equivalence): The authors prove that $\alpha$-cuts are exactly the split cuts for generalized corner relaxations. Specifically, every $\alpha$-cut is a split cut, and every split cut is dominated (rendered redundant) by an $\alpha$-cut. This establishes the CGF framework as a complete characterization of the split closure.
  2. Theorem 2 (Restriction): This theorem confirms that split cuts for finite-dimensional problems are restrictions of split cuts for the infinite-dimensional relaxation, reinforcing the "universal parent" concept.
  3. Theorem 3 (Integrality Gap): The authors construct a specific 3-variable pure-integer corner relaxation where the ratio between the true integer minimum and the split closure minimum is at least $1/12\epsilon$. As $\epsilon$ approaches zero, the split cuts fail to close the gap, proving that split cuts can be effectively useless even in pure-integer settings.

Discussion and Future Work

While this research provides a comprehensive geometric characterization of split cuts, it highlights several challenges for practical implementation. Although $\alpha$-cuts are shown to be "computable," the set of possible $\alpha$ vectors is infinite. The paper does not provide a specific heuristic or algorithm for selecting the optimal $\alpha$ vector within a commercial MIP solver.

Future research may extend this geometric lifting perspective to more complex cut types, such as triangle or quadrilateral cuts. Determining whether these higher-order disjunctive cuts also possess simple CGF equivalents remains an open and promising question in the field of mathematical optimization.

Summary updated

Abstract

Highlights•We analyze split cuts from the perspective of cut generating functions.•We show that k-cuts give all the split cuts for the mixed-integer corner relaxation.•This implies that all splits are restrictions of splits for the infinite relaxation.•We construct pure-integer IPs with arbitrarily bad split closure.
BibTeX
@article{basu2015characterization,
  author = {Amitabh Basu and Marco Molinaro},
  title = {{Characterization of the split closure via geometric lifting}},
  journal = {Eur. J. Oper. Res.},
  year = {2015},
  doi = {10.1016/j.ejor.2014.12.018},
}
Figure