Zurück zu den Preprints des Jahres 2002


Cutting Planes from a Mixed Integer Farkas Lemma

by Matthias Köppe, Robert Weismantel.

Series: 2002-23, Preprints

90C11 Mixed integer programming

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.

Farkas Lemma, mixed integer rounding cuts, lattice basis reduction