Return to Colloquia & Seminar listing
Computer-assisted Discovery and Automated Proofs of Cutting Plane Theorems
Student-Run Research Seminar| Speaker: | Yuan Zhou |
| Location: | 2112 MSB |
| Start time: | Wed, Nov 2 2016, 12:10PM |
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. We ask how much of this process can be automated: In particular, can we use algorithms to discover and prove theorems about cutting planes? We focus on general integer and mixed integer programming, and use the framework of cut-generating functions.
Using a metaprogramming technique followed by practical computations with semialgebraic cell complexes, we provide computer-based proofs for old and new cutting-plane theorems in Gomory-Johnson's model of cut generating functions.
RSVP for Pizza