02-23
Cutting Planes from a Mixed Integer Farkas Lemma
by Matthias Köppe; Robert Weismantel
Preprint series: 02-23, Preprints
- MSC:
- 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.