Integer Pivoting Revisited

by    R. T. Firla, U.-U. Haus, M. Köppe, B. Spille, R. Weismantel

Preprint series: 01-25 , Preprints

MSC:
90C10 Integer programming

Abstract: This paper deals with algorithmic issues related to the design of an augmentation algorithm for general and 0/1-integer programs. We recall the approach of integer pivoting and introduce the family of Gomory-Young augmentation vectors that can be derived from a simplex
tableau.

Furthermore, a technique of combining Gomory-Young vectors and combinatorial augmentation vectors in one augmentation scheme is presented. Two computational experiments demonstrate the potential of pivoting in an integer fashion.

Keywords: integer programming, primal algorithm, integer simplex, integral basis

Notes: First, fourth and fifth author supported by a Gerhard-Hess-Forschungsförderpreis (WE 1462/2-2) of the German Science Foundation (DFG) awarded to R. Weismantel.
Second and third author supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.

Upload: 2001-11-27-11-27


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.