01-05
A Primal All-Integer Algorithm Based on Irreducible Solutions
by Haus, Utz-Uwe; Köppe, Matthias; Weismantel, Robert
Preprint series: 01-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
Notes: All authors are supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. Last author is supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.