Optimization Online


Lattice based extended formulations for integer linear equality systems

Karen Aardal (karen.aardal***at***cwi.nl)
Laurence A. Wolsey (wolsey***at***core.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society