Department of Mathematics


  •  Cutting plane theorems for Integer Optimization and computer-assisted proofs
  •  02/03/2017
  •  10:00 AM - 11:00 AM
  •  1502 Engineering Building
  •  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.



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science