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