Advances in Mixed Integer Nonlinear Optimization
Many design, planning and decision problems arising in engineering, sciences, finance, and statistics can be mathematically modeled as Mixed-Integer Nonlinear Optimization (MINLO) problems. These six lectures will review the recent growth in the development of theory, algorithms and computational tools for MINLO. We will start with a gentle introduction to MINLO models and motivating practical applications. The next part of the course covers the branch-and-cut paradigm which is central to solving these problems followed by methods for convex MINLOs. Heuristic search, reformulation and presolving methods will be covered. The course concludes with discussions on the future trends of MINLO.
Outline of lectures: 1) Modeling and Applications of MINLO, 2) Fundamental Branch-and-Bound Algorithm, 3) Branch-and-Cut Algorithms, 4) Search Heuristics for MINLO, 5) Reformulations and Presolve Techniques, 6) Future Trends in MINLO (optimal experimental design, mixed-integer PDE-constrained optimization)
The moment-SOS hierarchy for polynomial optimization
Polynomial optimization consists of minimizing a polynomial of many real variables subject to polynomial equality and inequality constraints. It includes many difficult problem classes such as e.g. combinatorial optimization. The moment-sum-of-squares (moment-SOS) hierarchy is an approach to polynomial optimization that solves it globally at the price of solving a family of convex optimization problems of increasing size.
In these lectures we describe the main technical ingredients of the moment-SOS hierarchy: 1) the moment cone and its dual, 2) semidefinite relaxations of the moment cone and polynomial SOS approximations, 3) polynomial optimization and moment relaxations, 4) solution recovery with flat extension and with the Christoffel-Darboux polynomial.
The tropical geometry of shortest paths
The task of computing shortest paths in a finite directed graph is among the most basic problems in combinatorial optimization. For us it serves as one natural point of entry to tropical geometry. This leads us to interesting classification problems concerning convex polytopes, their triangulations, relevant algorithms and software. Eventually we circle back to shortest path problems, but now the edge lengths are not known exactly. We close with briefly mentioning applications concerning road networks and space flight.