Aarhus University Seal / Aarhus Universitets segl

Integer optimization, lattice point free sets and zero-coefficient cuts

Kent Andersen
(Otto-Von-Guericke University Magdeburg)
Beregningsmatematikseminar
Onsdag, 13 januar, 2010, at 14:15-15:15, in Aud. D3 (1531-215)
Abstrakt:
Integer optimization is an important component of Operations Research, and it is used for solving many problems that arise in practice. The state-of-the-art approach for solving integer problems uses so-called cutting-planes to cut off points that have fractional coordinates. Recently a new cutting-plane theory has emerged which is based on lattice-free sets. Lattice-free sets are convex sets whose interior does not contain integer points. The interior of a lattice-free set does therefore not contain any feasible solutions to an integer optimization problem. In this talk we survey this new approach and present some of the results that have been obtained. We also consider algorithmic consequences. In particular we present a new class of cutting planes that have a number of desirable theoretical properties. We call these cutting-planes for zero-coefficient cuts. In terms of quality, zero-coefficient cuts are those cuts that are violated the most, and in terms of efficiency, zero-coefficient cuts can be identified efficiently in polynomial time. Initial computational experiments suggest that zero-coefficient cuts could be an interesting class of cutting-planes to include in practical software for mixed integer optimization.