- 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/2007Entry Accepted: 02/28/2007Entry Last Modified: 03/01/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.