Lattice based extended formulations for integer linear equality systems

Karen Aardal and Laurence A. Wolsey
Additional contact information
Laurence A. Wolsey: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)

No 2007017, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: integer programming feasibility; integer width; branching directions; reduced lattice bases; Frobenius number (search for similar items in EconPapers)
Date: 2007-02-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2007.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2007017

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().