Non-standard approaches to integer programming

Karen Aardal, Robert Weismantel and Laurence Wolsey

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

Abstract: In this survey we address three of the principle algebraic approaches to integer programming. After introducing lattices and basis reduction, we first survey their use in integer programming, presenting among others Lenstra's algorithm that is polynomial in fixed dimension, and the solution of diophanine equations using basis reduction. The second topic concerns augmentation algorithms and test sets, including the role played by Hilbert and Grobner bases in the development of a primal approach to solve a family of problems for all right-hand sides. Thirdly we survey the group approach of Gomory, showing the importance of subadditivity in integer programming and the generation of valid inequalities, as well the relation to the parametric problem cited above of solving for all right hand sides.

Keywords: Integer Programming; Lattice Basis Reduction; Lenstra’s Algorithm; Test Sets; Augmentation Algorithms; Groebner Basis; Test Sets; Asymptotic Group Problem; Subadditivity; Corner Polyhedron. (search for similar items in EconPapers)
Date: 2000-01-01
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2000.html (text/html)

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:2000002

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 ().