Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Mixed-Integer Optimal Control - a biased overview

We give an overview of the group's activities in the recent years, with a focus on mixed-integer optimal control problems (MIOCPs) in differential equations, which have gained increasing interest over the last years. This is probably due to the fact that the underlying processes have a high potential for optimization. Typical examples are the choice of gears in transport or processes in chemical engineering involving on-off valves.

Although the first MIOCPs, namely the optimization of subway trains that are equipped with discrete acceleration stages, were already solved in the early eighties for the city of New York, the so-called indirect methods used there do not seem appropriate for generic large-scale optimal control problems with underlying nonlinear differential algebraic equation systems. Instead direct methods, in particular all-at-once approaches like the Direct Multiple Shooting Method, have become the methods of choice for most practical problems.

In direct methods infinite-dimensional control functions are discretized by basis functions and corresponding finite-dimensional parameters that enter into the optimization problem. The drawback of direct methods with binary control functions obviously is that they lead to high-dimensional vectors of binary variables. For many practical applications a fine control discretization is required, however. Therefore, techniques from mixed-integer nonlinear programming like Branch and Bound or Outer Approximation will work only on limited and small time horizons because of the exponentially growing complexity of the problem.

We propose to use an outer convexification with respect to the binary controls. The reformulated control problem has two main advantages compared to standard formulations or convexifications. First, especially for time-optimal control problems, the optimal solution of the relaxed problem will exhibit a bang-bang structure, and is thus already integer feasible. Second, theoretical results have recently been found that show that even for path-constrained and sensitivity-seeking arcs the optimal solution of the relaxed problem yields the exact lower bound on the minimum of the integer problem. This allows to calculate precise error estimates, if a coarser control discretization grid, a simplified switching structure for the optimization of switching times, or heuristics are used.

Type of Seminar:
Optimization and Applications Seminar
Prof. Sebastian Sager
Faculty of Mathematics, Otto-von-Guericke University, Magdeburg, Germany
Apr 30, 2012   16:30

HG G 19.1
Contact Person:

John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
Sebastian Sager studied in Heidelberg, Montpellier and Ho-Chi-Minh City. He received a diploma degree in Mathematics in 2001 and a PhD in 2006 from the University of Heidelberg. He was awarded with the GOR Dissertation Prize in 2006 and with the Klaus-Tschira-Prize for Public Understanding of Science in 2007. After postdoctoral research in Madrid Sager was head of a junior research group at the Interdisciplinary Center for Scientific Computing in Heidelberg. Since April 2012 he is full professor for Mathematical Optimization at the Otto-von-Guericke-University in Magdeburg. His main interests are mixed-integer nonlinear optimization and optimal control.