Cutting Planes from a Mixed Integer Farkas Lemma

by Matthias Köppe; Robert Weismantel


Preprint series: 02-23, Preprints

90C11 Mixed integer programming


Abstract: We present a mixed integer version of the lattice analogue of the Farkas Lemma. The result gives rise to a family of mixed-integer rounding cutting planes for mixed integer programs, which depend on the choice of a basis of a certain lattice. By choosing a Lovasz-reduced lattice basis, one can hope to generate numerically advantageous cutting planes.

Keywords: Farkas Lemma, mixed integer rounding cuts, lattice basis reduction

Notes: First named author supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. Second named author supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.