The integer hull of a convex rational polytope

Given $A\in Z^{m\times n}$ and $b\in Z^m$, we consider the integer program $\max \{c'x\vert Ax=b;x\in N^n\}$ and provide an equivalent and explicit linear program $\max \{\widehat{c}'q\vert M q=r;q\geq 0\}$, where $M,r,\widehat{c}$ are easily obtained from $A,b,c$ with no calculation. We also provide an explicit algebraic characterization of the integer hull of the convex polytope $P=\{x\in\R^n\vert Ax=b;x\geq0\}$. All strong valid inequalities can be obtained from the generators of a convex cone whose definition is explicit in terms of $M$.


Technical report #03018, LAAS, Toulouse, January 2003. Discr. Comput. Geom. 32 (2004), 129--139