Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

ABOUT THE RESEARCH AREA:

An example problem explains best what Mixed Integer Optimization is about: A traveler needs to visit a number of cities on a roundtrip, starting from and returning to her home city. The cities can be visited in any order, but of course the possible routes are very different in their length. In addition, several modes of transportation are available; there is a fixed budget for the travel costs, and the roundtrip must be completed within 2 weeks. The traveler wishes to choose a route and modes of transportation, so as to keep the overall carbon dioxide impact of the trip as low as possible. A plan for the roundtrip can be mathematically described (modeled) using a large collection of tiny yes--no decisions, such as "use a bus from city A to city B, or not." These yes/no decisions become mathematical variables that are only allowed to take the integer values 0 ("no") or 1 ("yes"), such as on budget and on time, can then be expressed using inequalities in these variables. The goal regarding the CO2 impact is expressed as a function (the objective function), which we wish to minimize. Mathematical models like this are called integer optimization problems. When not just integer, but also real variables are present, we speak of mixed integer optimization problems. They appear in countless critical applications in all areas of business and industry. In addition, the methods of optimization are very powerful mathematical tools that are used in many academic disciplines, and often serve as a key methodical tool in successful interdisciplinary cooperations. In the field of mathematical optimization, we study how to set up these models in the most effective way, develop efficient computer-implementable methods to solve the optimization problems, and prove theorems about the properties of optimal solutions. A key ingredient in numerical solvers for mixed integer optimization problems are so-called cutting planes. Good ("strong") cutting planes arise from detailed studies of the convex geometry and polyhedral combinatorics of the problem.

ABOUT THE TALK:

I present a contemporary research direction in cutting planes for mixed integer optimization problems and explain recent results obtained with my research group (Krener Assist. Prof. Amitabh Basu and 5-th year graduate student Robert Hildebrand). The Gomory-Johnson infinite group problem is an infinite-dimensional abstraction of mixed-integer linear programs for the purpose of deriving cutting planes. One studies the convex geometry of this problem using tools from real analysis and group theory. We give an algorithm for testing the extremality of minimal valid functions for the infinite group problem on $R^1/Z^1$, that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions, which can be tested algorithmically, for deciding extremality in this important class of valid minimal functions. We also present an interesting irrational function. We also prove that any minimal valid function for the $k$-dimensional infinite group relaxation (on $R^k/Z^k$) that is piecewise linear with at most $k+1$ slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes the famous 2-slope theorem of Gomory and Johnson for $k=1$, and a corresponding result by Cornu\'ejols and Molinaro for $k=2$.

Pizza and soda will be provided.