Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Abstract: Integer programming, the problem of finding an integral point in a polyhedron which minimizes a linear function, is NP-hard. Yet because of its practical importance, many different techniques have been developed to solve this problem. Cutting planes, or linear inequalities satisfied by all integral points in a polyhedron, are very important tools for integer programming. The remarkable aspect of cutting planes is the following: 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. Joint work with Oktay Gunluk and Andrea Lodi.