Zurück zu den Preprints des Jahres 2001


2001-05

A Primal All-Integer Algorithm Based on Irreducible Solutions

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


Series: 2001-05, 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 various
versions of our algorithm are finite. It is a major concern in this paper to
show how the subproblem of replacing a column can be accomplished
effectively. For computational results we refer to a companion paper.

Keywords:
Integer programming, Hilbert bases, primal methods