Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

I review the field of Integer Linear Optimization, my main subject area. Using an example from an application domain, I illustrate the limitations of the state-of-the-art, "dual-type" methods. In the recent past, I have developed a new class of "primal-type" algorithms (joint work with R. Weismantel and other authors) that are based on algorithmic theories for minimal generating sets of lattice point sets. Though being a computational success for large-scale integer programs, the current implementations of the new methods still do not beat the dual-type methods. This suggests to develop combined, "primal-dual" algorithms for Integer Programming. I explain the goals and challenges of such an algorithm. A very powerful new technique from enumerative combinatorics is the use of A. Barvinok's (1994) calculus of "short" rational generating functions. For the problem of optimizing an arbitrary polynomial function over the mixed-integer points of a convex polytope in arbitrary fixed dimension, we prove the strongest possible algorithmic approximation result, a so-called FPTAS (joint work with J. De Loera et al.). To complement this complexity result, I present recent work on an "irrational" primal perturbation method, which dramatically improves the practical performance of short rational generating functions. An extension of Barvinok's method, the Barvinok--Woods (2003) theory of integer projections, has important consequences on even harder optimization problems. I present recent results, including bilevel integer linear optimization problems and optimization problems over pure Nash equilibria of certain games (joint work with M. Queyranne and other authors). I also report on current effort to obtain the first-ever implementation of the Barvinok--Woods integer projection method (joint work with S. Verdoolaege).

Job Talk, Refreshments provided