Can I read Lattice Based Extended Formulations for Integer Linear Equality Systems on EtoBox?

Lattice Based Extended Formulations for Integer Linear Equality Systems by Aardal, Karen; Wolsey, Laurence A. is a scholarly article available to read on EtoBox.

What is Lattice Based Extended Formulations for Integer Linear Equality Systems about?

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.

Author

Aardal, Karen; Wolsey, Laurence A.

Published

2007

Language

EN