Mixed-integer optimal control

A short introduction to the underlying idea of how to decompose mixed-integer optimal control problems can be found in these slides on PDE constrained mixed-integer optimal control.

Mixed-integer optimal control problems (MIOCPs) in differential equations 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. Also experimental design problems for continuous processes can be formulated as MIOCPs.

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.

The group actively contributes to the creation of an online benchmark library for mixed-integer optimal control problems. Several of the applications that could be solved with our algorithms are listed there.

Selected publications



AuthorTitleYearJournal/ProceedingsReftypeLink
Huschto, T., Podolskij, M., Sager, S. The asymptotic error of chaos expansion approximations for stochastic differential equations 2019 Modern Stochastics: Theory and Applications   article DOI
 
BibTeX:
@article{Huschto2019,
    author = {Huschto, T. and Podolskij, M. and Sager, S.},
    title = {The asymptotic error of chaos expansion approximations for stochastic differential equations},
    journal = {Modern {S}tochastics: {T}heory and {A}pplications},
    year = {2019},
    volume = {6},
    number = {2},
    pages = {145--165},
    doi = {10.15559/19-VMSTA133}
}
Jost, F., Sager, S., Le, T. A Feedback Optimal Control Algorithm with Optimal Measurement Time Points 2017 Processes   article
url  
BibTeX:
@article{Jost2017,
    author = {Jost, F. and Sager, S. and Le, T.T.T.},
    title = {A Feedback Optimal Control Algorithm with Optimal Measurement Time Points},
    journal = {Processes},
    year = {2017},
    volume = {5},
    number = {10},
    pages = {1--19},
    url = {http://www.mdpi.com/2227-9717/5/1/10}
}
Matke, C., Bienstock, D., Munoz, G., Yang, S., Kleinhans, D., Sager, S. Robust optimization of power network operation: storage devices and the role of forecast errors in renewable energies 2017 Studies in Computational Intelligence: Complex Networks and Their Applications V   inproceedings DOI
 
BibTeX:
@inproceedings{Matke2017,
    author = {Matke, C. and Bienstock, D. and Munoz, G. and Yang, S. and Kleinhans, D. and Sager, S.},
    title = {Robust optimization of power network operation: storage devices and the role of forecast errors in renewable energies},
    booktitle = {Studies in Computational Intelligence: Complex Networks and Their Applications V},
    year = {2017},
    number = {693},
    pages = {809--820},
    doi = {10.1007/978-3-319-50901-3}
}
Matke, C., Medjroubi, W., Kleinhans, D., Sager, S. Structure Analysis of the German Transmission Network Using the Open Source Model SciGRID 2017 Advances in Energy System Optimization   inproceedings
 
BibTeX:
@inproceedings{Matke2017a,
    author = {Matke, Carsten and Medjroubi, Wided and Kleinhans, David and Sager, Sebastian},
    title = {Structure Analysis of the German Transmission Network Using the Open Source Model SciGRID},
    booktitle = {Advances in Energy System Optimization},
    publisher = {Springer International Publishing},
    year = {2017},
    editor = {Bertsch, Valentin and Fichtner, Wolf and Heuveline, Vincent and Leibfried, Thomas},
    pages = {177--188},
    address = {Cham}
}
Huschto, T., Sager, S. Pricing Conspicuous Consumption Products in Recession Periods with Uncertain Strength 2014 European Journal of Decision Processes   article
url  
BibTeX:
@article{Huschto2014,
    author = {Huschto, T. and Sager, S.},
    title = {{P}ricing {C}onspicuous {C}onsumption {P}roducts in {R}ecession {P}eriods with {U}ncertain {S}trength},
    journal = {{E}uropean {J}ournal of {D}ecision {P}rocesses},
    year = {2014},
    volume = {2},
    number = {1--2},
    pages = {3--30},
    url = {http://www.optimization-online.org/DB_HTML/2012/09/3620.html}
}
Huschto, T., Sager, S. Solving Stochastic Optimal Control Problems by a Wiener Chaos Approach 2014 Vietnam Journal of Mathematics   article
url  
BibTeX:
@article{Huschto2014a,
    author = {Huschto, T. and Sager, S.},
    title = {{S}olving {S}tochastic {O}ptimal {C}ontrol {P}roblems by a {W}iener {C}haos {A}pproach},
    journal = {{V}ietnam {J}ournal of {M}athematics},
    year = {2014},
    volume = {42},
    number = {1},
    pages = {83--113},
    url = {https://mathopt.de/publications/Huschto2014a.pdf}
}
Huschto, T. Numerical Methods for Random Parameter Optimal Control and the Optimal Control of Stochastic Differential Equations 2014 School: University Heidelberg   phdthesis
url  
BibTeX:
@phdthesis{Huschto2014b,
    author = {Huschto, T.},
    title = {{N}umerical {M}ethods for {R}andom {P}arameter {O}ptimal {C}ontrol and the {O}ptimal {C}ontrol of {S}tochastic {D}ifferential {E}quations},
    school = {University Heidelberg},
    year = {2014},
    url = {https://mathopt.de/publications/Huschto2014.pdf}
}

Further references of the MathOpt group can be found on this page.

  • currently no upcoming news

...more

Prof. Dr. Sebastian Sager
Head of MathOpt group
at the Institute of Mathematical Optimization
at the Faculty of Mathematics
at the Otto-von-Guericke University Magdeburg

Universitätsplatz 2, 02-224
39106 Magdeburg, Germany

: +49 391 67 58745
:

Susanne Heß

Universitätsplatz 2, 02-201
39106 Magdeburg, Germany

: +49 391 67 58756
:

  • currently no upcoming news

...more

Prof. Dr. Sebastian Sager
Head of MathOpt group
at the Institute of Mathematical Optimization
at the Faculty of Mathematics
at the Otto-von-Guericke University Magdeburg

Universitätsplatz 2, 02-224
39106 Magdeburg, Germany

: +49 391 67 58745
:

Susanne Heß

Universitätsplatz 2, 02-201
39106 Magdeburg, Germany

: +49 391 67 58756
: