*Wissenschaftliches Programm* † *Liste der Vortragenden*

Sektion 15
Dienstag, 19.09.2000, 15.00–15.20 Uhr, WIL C 103

Using Lattice Operations for Finding Good Solutions

Utz-Uwe Haus, Otto-von-Guericke-Universitšt Magdeburg

Primal methods have been the starting point for many deep algorithmic results in integer programming. Augmentation algorithms are used successfully to solve well-known combinatorial optimization problems such as Max Flow, Min-Cost Flow and Weighted Matroid Intersection. Since the knowledge about the combinatorial structure of the individual problem is crucial to their success, no theory enters the primal phase of today’s integer programming algorithms.

We present an augmentation algorithm that is applicable to general integer programs, relying solely on the discrete nature of the set of feasible solutions: The lattice basis reduction algorithm of Lenstra, Lenstra and Lovász can be used to compute short lattice vectors. By adapting the norm used for reduction we can suitably adapt the notion of ‘shortness’ to the problem instance and - iteratively - to the current feasible solution. The resulting ‘short’ lattice vectors can be used to augment the current solution. Promising computational results for instances from the MIPLIB as well as randomly generated Cornuéjols-Dawande (market-split) instances will be presented.