01-25
Integer Pivoting Revisited
by Firla, R. T.; Haus, U.-U.; Köppe, M.; Spille, B.; Weismantel, R.
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.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.