Return to Colloquia & Seminar listing
Computational cutgeneratingfunctionology: Certifying next-generation cutting planes for mixed integer linear programming
Faculty Research Seminar| Speaker: | Matthias Köppe, UC Davis |
| Related Webpage: | https://www.math.ucdavis.edu/~mkoeppe/ |
| Location: | Zoom |
| Start time: | Tue, Jan 12 2021, 12:10PM |
Mixed-integer optimization (MIP) is a powerful mathematical decision-making technology and a key technology of operations research, data sciences, and artificial intelligence.
MIP practitioners nowadays can solve large-scale mixed integer optimization problems to optimality or provable near-optimality by competent modelization and running a black-box branch-and-cut solver. This technology was enabled to a large part by the dramatic revival of results by Gomory on valid inequalities for diophantine inequality systems -- which had been written off as "purely theoretical" in the literature of the 1970s to early 1990s.
Challenging new applications and increased data sizes now require the development of next-generation general-purpose cutting-plane systems.
In my talk I will give a brief review of cutgeneratingfunctionology, an infinite-dimensional framework for analyzing such cutting-plane systems, and highlight some research challenges in this framework. I will then introduce computational methods, including automated proof techniques, that address these difficulties.
Computational cutgeneratingfunctionology is one of the topics of my recently awarded NSF grant "Next-Generation Cutting Planes: Compression, Automation, Diversity, and Computer-Assisted Mathematics (CAD/CAM)". I am hoping to recruit graduate students who are interested in working with me on this project.