Zurück zu den Preprints des Jahres 2001


2001-25

Integer Pivoting Revisited

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


Series: 2001-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