Return to Colloquia & Seminar listing
Integer optimization, cutting planes, and computer-assisted proofs
PDE & Applied Mathematics| Speaker: | Matthias Koeppe, UC Davis |
| Location: | 1147 MSB |
| Start time: | Fri, Sep 30 2016, 4:10PM |
Description
Optimization problems with integer variables are a class of mathematical models that are popular in a wide range of applications because of their great modeling power and because of the availability of convenient solvers. The modeling power comes at a high price: Integer optimization problems are typically very hard to solve, both in theory (NP-hardness, inapproximability, ...) and practice.
A key ingredient in state-of-the-art solvers for integer optimization problems are cutting-plane algorithms. The need for next-generation cutting planes, prompted by ever-larger applications and models, has led to a recent trend, which revisits and extends foundational work in integer optimization, by Ralph Gomory in the 1960s and Gomory--Johnson in the early 1970s, under the name of "cut-generating functions".
I will present some aspects of this theory and in particular recent work on computer-assisted discovery and proofs of theorems about cut-generating functions.
My talk is based on joint work with former Krener Assistant Professor Amitabh Basu, my former student Robert Hildebrand, and my current student Yuan Zhou.