Optimization Seminar: Prof. Matthias Koeppe (University of California, Davis) @ Whitehead 304

Title: Inverse semigroup theory of cutting planes for integer linear optimization
Abstract: MIP practitioners can solve large-scale mixed integer optimizationproblems to optimality or near-optimality by competent modelizationand use of branch-and-cut solvers.  This technology was enabled to alarge part by the revival of Gomory’s classic general-purpose cuttingplanes such as the Gomory mixed integer cut. In the theory of such general-purpose cutting planes (validinequalities) the traditional, finite-dimensional techniques ofpolyhedral combinatorics are complemented by infinite-dimensionalmethods, the study of cut-generating functions. In my talk I will introduce the classic Gomory-Johnson model, auniversal relaxation of integer programs in the form of a singleconstraint in infinitely many nonnegative integer variables.  Thenondominated valid inequalities (cut-generating functions) for thismodel, “minimal functions”, are characterized by functionalinequalities such as subadditivity. Given a minimal function, we are interested in finding improvingdirections that lead to stronger cuts and eventually to “extremefunctions”, which cannot be strengthened further — an analogue offacet-defining inequalities. I will present an inverse semigroup theory for minimal functions,which enables us to obtain a complete description of the space of”improving directions” (perturbations) of a minimal function.  This isjoint work with Robert Hildebrand and Yuan Zhou, which appeared inIPCO 2019; a full paper is available at https://arxiv.org/abs/1811.06189 .