Lattice based extended formulations for integer linear equality systems
(2007)
Files
DP-karen12-02-07.pdf
Open Access - Adobe PDF
- 214.41 KB
Details
- Authors
- Abstract
- We study different extended formulations for the set X = {x [belong] Z exp.n | Ax = Ax exp.0} in order to tackle the feasibility problem for the set X+ = X [intersection] Z+ exp.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.
- Affiliations
Citations
Aardal, K., & Wolsey, L. (2007). Lattice based extended formulations for integer linear equality systems (CORE Discussion Papers 2007/17). https://hdl.handle.net/2078.5/129351