Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Cutting planes in mixed integer optimizationStudent-Run Applied & Math Seminar
|Speaker: ||Matthias Koeppe, University of California, Davis|
|Location: ||2112 MSB|
|Start time: ||Fri, Feb 15 2013, 12:10PM|
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.