Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Computational cutgeneratingfunctionology: Certifying next-generation cutting planes for mixed integer linear programming

Mathematics of Data & Decisions

Speaker: Matthias Köppe, UC Davis
Related Webpage: https://www.math.ucdavis.edu/~mkoeppe/
Location:
Start time: Tue, Jan 12 2021, 12:10PM

This is a cross-listing of https://www.math.ucdavis.edu/research/seminars/?ta...

(Faculty Research seminar)

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.