Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Computer-assisted Discovery and Automated Proofs of Cutting Plane Theorems

Student-Run Applied & Math 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