Zurück zu den Preprints des Jahres 1999


1999-22

A Primal Analogue of Cutting Plane Algorithms

by Robert T. Firla, Bianca Spille, Robert Weismantel.


Series: 1999-22, Preprints

MSC:
90C10 Integer programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

Abstract:
This paper deals with algorithmic issues related to the design of an
augmentation algorithm for general integer programs.
It is shown that every phase of a primal method has
a natural analogue in cutting plane algorithms.
In particular, the role that the Chvátal-Gomory cuts
play in cutting plane algorithms
is taken on by so-called Gomory-Young augmentation vectors.
The latter family of vectors can naturally be derived from a simplex tableau.

There is also a primal counterpart of families of
combinatorial cutting planes.
To demonstrate this we introduce an augmentation network
for the intersection of any two integer programs.
Paths and cycles in this network correspond to candidates for
improving feasible solutions.
This network gives rise to an algorithmic characterization
of the weighted bipartite b-matching problem.

Keywords:
primal algorithm, local search, augmentation network, bipartite b-matching, Gomory-Young vectors