Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.

A key ingredient in state-of-the-art solvers for integer optimization problems are cutting-plane algorithms. The need for next-generation cutting planes, prompted by ever-larger applications and models, has led to a recent trend, which revisits and extends foundational work in integer optimization by Ralph Gomory in the 1960s and Gomory–Johnson in the early 1970s, under the name of cut-generating functions. In this dissertation, we focus on the cut-generating functions in the single row Gomory–Johnson infinite group relaxation model for integer optimization problems.

The proofs of cutting planes theorems in the literature 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?

We develop a software for investigations with cut-generating functions, which implements a grid-free algorithmic extremality test. We conduct a computer-based search that leads to the discovery of new cut-generating functions, whose existence settles several open questions. Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting-plane theorems.

This dissertation also addresses the theoretical aspects of cut-generating functions. We improve the general theory of effective perturbations of minimal valid functions, which enables the grid-free algorithmic extremality test. We investigate the fine structure of a space of cut-generating functions, underlining the exceptional place that two-sided discontinuous functions take in the theory of the Gomory–Johnson functions. We establish a clear relation of three competing notions of facets in the infinite-dimensional Gomory–Johnson model, resolving a longstanding mystery.