Mixed Integer Optimization: A Geometric View
Within the past 40 years many researchers have contributed to the development of a theory of Linear Discrete Optimization that allows us to solve many practical applications today that were considered unsolvable ten or twenty years ago.
The situation is completely different when one considers mixed integer optimization problems, i.e., systems of linear inequalities and equations for which parts of the variables are continous and the other part is required to be integral. The presence of both types of variables results in a significant increase in complexity with respect to geometric, algebraic and combinatorial properties.
In this survey we develop a geometric approach to mixed integer optimization. Indeed, since more than 30 years it is an open question to invent a theory of mixed integer cutting planes that allows us to design a finite cutting plane algorithm. We present a geometric approach based on lattice point free bodies. Besides giving results about finite convergence of a corresponding cutting plane algorithm we also explore new Mixed Integer Farkas type Lemmas for linear systems and establish a link between lattice point free polyhedra and the derivation of cutting planes from several rows of a simplex tableau.
Robert Weismantel, University of Magdeburg, Germany