Let $A \in \mathbb{ Z}^{ m \times n}$ be an integer matrix with components 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 $t \in \mathbb{ Z}^{ m'}$ such that the integer hull of the polyhedron $P = \{ x \in \mathbb{ R}^n \colon Ax \leq b\}$ is described by $P_I = \{ x \in \mathbb{ R}^n \colon Bx \leq t\}$. Our \emph{ main result} is that $t$ is an \emph{ 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 $\Delta$ and $n$ only. An application of this result is the solution of an open problem posed by Cslovjecsek et al.~(SODA 2024) concerning the complexity of \emph{ 2-stage-stochastic integer programming} problems. The main tool of our proof is the classical theory of \emph{ Chv\'atal-Gomory cutting planes} and the \emph{ elementary closure} of rational polyhedra.
Categories: cs.CC math.OC