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.