A parameterized linear formulation of the integer hull
Let π΄ ββ€πΓπ be an integer matrix with entries bounded by Ξ in absolute value. Cook et al. (1986) have shown that there exists a universal matrix π΅ ββ€πβ²Γπ with the following property: For each π ββ€π, there exists a π‘ ββ€πβ² such that the integer hull of the polyhedron π ={π₯ ββπ :π΄β’π₯ β€π} is described by ππΌ ={π₯ ββπ :π΅β’π₯ β€π‘}. Our main result is that π‘ is an affine function of π as long as π is from a fixed equivalence class of the lattice π· β β€π. Here π· ββ is a number that depends on π and Ξ only. Furthermore, π· as well as the matrix π΅ can be computed in time depending on π and Ξ only. An application of this result is the solution of an open problem posed by Cslovjecsek et al. (SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems. The main tool of our proof is the classical theory of ChvΓ‘tal-Gomory cutting planes and the elementary closure of rational polyhedra.
2026-01
Philadelphia, PA
9781611978971
4560
4571
REVIEWED
EPFL