Zurück zu den Preprints des Jahres 2002


2002-23

Cutting Planes from a Mixed Integer Farkas Lemma

by Matthias Köppe, Robert Weismantel.


Series: 2002-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