Return to Colloquia & Seminar listing
Integer optimization, cutting planes, and computer-assisted proofsPDE and Applied Math Seminar
|Speaker: ||Matthias Koeppe, UC Davis|
|Location: ||1147 MSB|
|Start time: ||Fri, Sep 30 2016, 4:10PM|
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
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.