A parameterized linear formulation of the integer hull

Let \(A \in \mathbb{Z}^{m \times n}\) be an integer matrix with entries bounded by \(\Delta\) in absolute value. Cook et al. (1986) have shown that there exists a universal matrix \(B \in \mathbb{Z}^{m' \times n}\) with the following property: For each \(b \in \mathbb{Z}^m\), there exists a \(t \in \mathbb{Z}^{m'}\) such that the integer hull of the polyhedron \(P = \{x \in \mathbb{R}^n : Ax \le b\}\) is described by \(P_I = \{x \in \mathbb{R}^n : Bx \le t\}\). Our main result is that \(t\) is an affine function of \(b\) as long as \(b\) is from a fixed equivalence class of the lattice \(D \cdot \mathbb{Z}^m\). Here \(D \in \mathbb{N}\) is a number that depends on \(n\) and \(\Delta\) only. Furthermore, \(D\) as well as the matrix \(B\) can be computed in time depending on \(n\) and \(\Delta\) 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.