Non-standard approaches to integer programming

Journal article (2002)

Authors

K.I. Aardal Universiteit Utrecht, Université Catholique de Louvain

Robert Weismantel Université Catholique de Louvain, Otto von Guericke University Magdeburg

Laurence A. Wolsey Université Catholique de Louvain

Affiliation

External organisation

Lattice basis reduction Integer programming Lenstra's algorithm Test sets Augmentation algorithms Gröbner basis Asymptotic group problem Subadditivity Corner polyhedron

To reference this document use:

http://resolver.tudelft.nl/uuid:37b53d25-f8b1-4c1a-83cb-ebb17e2581c5

More Info

expand_more

Published Date

2002

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

In this survey we address three of the principal 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 Gröbner 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.