 |
|
sponsored by
Title : Mixed-integer Rounding Cutting Planes for Integer Programs
Date : Sep 24, 2007
Speaker : Sanjeeb Dash, Ph.D.
Affiliation : Mathematical Sciences Department,IBM, T. J. Watson Research Center , New York
Abstract
The integer programming problem - the problem of finding an integral point in a polyhedron minimizing a linear function - is of great practical importance. Cutting planes, or linear inequalities satisfied by all integral points in a polyhedron, are both very useful in solving practical integer programs, and also have interesting theoretical properties. For example, the work of Gomory implies that any integer program (and therefore any problem in NP) can be solved by generating an appropriate sequence of cutting planes. In my talk I will focus on the most important class of general cutting planes, namely mixed-integer rounding (MIR) cutting planes. I will describe recent work on the separation problem for MIR cutting planes - given a point contained in a polyhedron, test if there exists an MIR cutting plane violated by this point or prove that none exists - and explain how this work is useful in solving integer programming problems. I will also discuss results on the strength of MIR cutting planes. Some of these results explain why MIR cutting planes are very useful compared to other well-known classes of cutting planes; others establish that MIR cutting plane based algorithms can have exponential complexity in the worst case. This talk is based on joint work with a number of authors, especially Oktay Gunluk and Andrea Lodi.
Biosketch
Sanjeeb Dash is a Research Staff Member in the Mathematical Sciences Department at the IBM T. J. Watson Research Center in New York . His primary area of research is Computational discrete optimization. He has recently been working on finding better ways to solve integer programs via cutting planes.
