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.