99-22
A Primal Analogue of Cutting Plane Algorithms
by Robert T. Firla; Bianca Spille; Robert Weismantel
Preprint series: 99-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\xe1tal-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
Notes: The work of the three authors is supported by a ``Gerhard-Hess-Forschungsf rderpreis\'\' (WE 1462/2-2) of the German Science Foundation (DFG) awarded to R. Weismantel. The third author is also supported by the ``Kultusministerium Sachsen-Anhalt\'\' and an EC DONET Project.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.