Lattice based extended formulations for integer linear equality systems
| dc.creator | Aardal, Karen | |
| dc.creator | Wolsey, Laurence A. | |
| dc.date | 2007-02-28 | |
| dc.date.accessioned | 2026-07-07T07:49:23Z | |
| dc.date.available | 2026-07-07T07:49:23Z | |
| dc.description | 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. | |
| dc.description | uses packages amsmath and amssymb | |
| dc.identifier | https://arxiv.org/abs/math/0702881 | |
| dc.identifier | http://arxiv.org/abs/math/0702881 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/124827 | |
| dc.subject | Optimization and Control | |
| dc.subject | Number Theory | |
| dc.subject | 90C10;45A05;11Y50 | |
| dc.title | Lattice based extended formulations for integer linear equality systems | |
| dc.type | text |