Zurück zu den Preprints des Jahres 2000


2000-16

The Integral Basis Method for Integer Programming

by Haus, Utz-Uwe, Köppe, Matthias, Weismantel, Robert.


Series: 2000-16, Preprints

MSC:
90C10 Integer programming

Abstract:
This paper introduces an exact algorithm for solving integer
programs, neither using cutting planes nor enumeration techniques.
It is a primal augmentation algorithm that relies on iteratively
substituting one column by columns that correspond to irreducible
solutions of certain linear diophantine inequalities. We prove that
our algorithm is finite and demonstrate its potential by testing it
on some instances of the MIPLIB with several hundred variables.

Keywords:
Integer programming, Hilbert bases, primal methods