Lattice based extended formulations for integer linear equality systems

Karen Aardal (karen.aardalcwi.nl)
Laurence A. Wolsey (wolseycore.ucl.ac.be)

Abstract: We study different extended formulations for the set $X =\{x\in\mathbb{Z}^n \mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X \cap \mathbb{Z}^n_+$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_+)$, but rather to reformulate in such a way that the new variables introduced provide good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible. For the case that $A$ has one row $a$ we analyze the reformulations in more detail. In particular, we determine the integer width of the extended formulations in the direction of the last coordinate, and derive a lower bound on the Frobenius number of $a$. We also suggest how a decomposition of the vector $a$ can be obtained that will provide a useful extended formulation. Our theoretical results are accompanied by a small computational study.

Keywords: integer programming feasibility; integer width; branching directions; reduced lattice bases;Frobenius number

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: PNA-R0702, CWI, P.O. Box 94079, 1090 GB Amsterdam, February, 2007

Download: [PDF]

Entry Submitted: 02/28/2007
Entry Accepted: 02/28/2007
Entry Last Modified: 03/01/2007

Modify/Update this entry