The integer hull of a convex rational polytope

Jean B. Lasserre (lasserrelaas.fr)

Abstract: 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$.

Keywords: Integer programming; convex polytope; integer hull

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Polyhedra )

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

Download:

Entry Submitted: 04/26/2003
Entry Accepted: 04/26/2003
Entry Last Modified: 05/19/2004

Modify/Update this entry