Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.