Title: Cutting plane theorems for Integer Optimization and computer-assisted proofs

Date: 02/03/2017

Time: 10:00 AM - 11:00 AM

Place: 1502 Engineering Building

Speaker: Yuan Zhou, UC Davis

Optimization problems with integer variables form a class of mathematical
models that are widely used in Operations Research and Mathematical Analytics.
They provide a great modeling power, but it comes at a high price: Integer
optimization problems are typically very hard to solve, both in theory and practice.
The state-of-the-art solvers for integer optimization problems use cutting-plane
algorithms. Inspired by the breakthroughs of the polyhedral method for
combinatorial optimization in the 1980s, generations of researchers have studied the
facet structure of convex hulls to develop strong cutting planes. However, the
proofs of cutting planes theorems were hand-written, and were dominated by
tedious and error-prone case analysis.
We ask how much of this process can be automated: In particular, can we use
algorithms to discover and prove theorems about cutting planes? I will present our
recent work towards this objective. We hope that the success of this project would
lead to a tool for developing the next-generation cutting planes that answers the
needs prompted by ever-larger applications and models.