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
@article{Buerger2023,
author = {B{\"u}rger, Adrian and Zeile, Clemens and Altmann-Dieses, Angelika and Sager, Sebastian and Diehl, Moritz},
title = {A Gauss-Newton-based Decomposition Algorithm for Nonlinear Mixed-Integer Optimal Control Problems},
journal = {Automatica},
year = {2023},
volume = {152},
pages = {110967}
}
@article{Hahn2023,
author = {Hahn, Mirko and Leyffer, Sven and Sager, Sebastian},
title = {Binary Optimal Control by Trust-Region Steepest Descent},
journal = {Mathematical Programming},
year = {2023},
volume = {197},
number = {1},
pages = {147--190},
doi = {10.1007/s10107-021-01733-z}
}
@article{Manns2023,
author = {Manns, Paul and Hahn, Mirko and Kirches, Christian and Leyffer, Sven and Sager, Sebastian},
title = {On convergence of binary trust-region steepest descent},
journal = {Journal of Nonsmooth Analysis and Optimization},
publisher = {Episciences. org},
year = {2023},
volume = {4},
pages = {10164},
doi = {10.46298/jnsao-2023-10164}
}
@article{Thuenen2022,
author = {Th\"unen, A. and Leyffer, S. and Sager, S.},
title = {State Elimination for Mixed-Integer Optimal Control of Partial Differential Equations by Semigroup Theory},
journal = {Optimal Control, Applications and Methods},
year = {2022},
volume = {43},
number = {3},
pages = {867--883},
doi = {10.1002/oca.2861}
}
@article{Zeile2022,
author = {Zeile, Clemens and Weber, Tobias and Sager, Sebastian},
title = {Combinatorial integral approximation decompositions for mixed-integer optimal control},
journal = {Algorithms},
publisher = {MDPI},
year = {2022},
volume = {15},
number = {4},
pages = {121},
url = {https://www.mdpi.com/1999-4893/15/4/121/pdf}
}
@article{Robuschi2021,
author = {Robuschi, N. and Zeile, C. and Sager, S. and Braghin, F.},
title = {Multiphase Mixed-Integer Nonlinear Optimal Control of Hybrid Electric Vehicles},
journal = {Automatica},
year = {2021},
volume = {123},
pages = {109325},
url = {https://optimization-online.org/?p=15819}
}
@article{Sager2021b,
author = {Sager, Sebastian and Zeile, Clemens},
title = {On Mixed-Integer Optimal Control with Constrained Total Variation of the Integer Control},
journal = {Computational Optimization and Applications},
publisher = {Springer},
year = {2021},
volume = {78},
number = {2},
pages = {575--623},
url = {https://optimization-online.org/?p=16059},
doi = {10.1007/s10589-020-00244-5}
}
@article{Zeile2021b,
author = {Zeile, C. and Robuschi, N. and Sager, S.},
title = {Mixed-Integer Optimal Control under Minimum Dwell Time Constraints},
journal = {Mathematical Programming},
year = {2021},
volume = {188},
number = {2},
pages = {653--694},
url = {https://link.springer.com/article/10.1007/s10107-020-01533-x},
doi = {10.1007/s10107-020-01533-x}
}
@inproceedings{Buerger2020,
author = {B\"urger, A. and Zeile, C. and Hahn, M. and Altmann-Dieses, A. and Sager, S. and Diehl, M.},
title = {pycombina: An Open-Source Tool for Solving Combinatorial Approximation Problems arising in Mixed-Integer Optimal Control},
journal = {IFAC},
year = {2020},
volume = {53},
pages = {6502--6508},
doi = {10.1016/j.ifacol.2020.12.1799}
}
@article{Buerger2019,
author = {Buerger, A. and Zeile, C. and Altmann-Dieses and A., Sager, S. and Diehl, M.},
title = {Design, Implementation and Simulation of an MPC algorithm for Switched Nonlinear Systems under Combinatorial Constraints},
journal = {Process Control},
year = {2019},
volume = {81},
pages = {15--30},
url = {https://mathopt.de/publications/Buerger2019.pdf}
}
@inproceedings{Buerger2018a,
author = {Buerger, A. and Zeile, C. and Altmann-Dieses and A., Sager, S. and Diehl, M.},
title = {An Algorithm for Mixed-Integer Optimal Control of Solar Thermal Climate Systems with MPC-capable runtime},
journal = {Proceedings of the European Control Conference (ECC)},
year = {2018},
url = {https://ieeexplore.ieee.org/document/8550424}
}
@article{Jung2018,
author = {Jung, M. N. and Kirches, C. and Sager, S. and Sass, S.},
title = {Computational Approaches for Mixed Integer Optimal Control Problems with Indicator Constraints},
journal = {Vietnam Journal of Mathematics},
year = {2018},
volume = {46},
pages = {1023--1051},
doi = {10.1007/s10013-018-0313-z}
}
@article{Jung2015,
author = {Jung, M. and Reinelt, G. and Sager, S.},
title = {{T}he {L}agrangian {R}elaxation for the {C}ombinatorial {I}ntegral {A}pproximation {P}roblem},
journal = {{O}ptimization {M}ethods and {S}oftware},
year = {2015},
volume = {30},
number = {1},
pages = {54--80}
}
@article{Sager2015,
author = {Sager, S. and Claeys, M. and Messine, F.},
title = {{E}fficient upper and lower bounds for global mixed-integer optimal control},
journal = {{J}ournal of {G}lobal {O}ptimization},
year = {2015},
volume = {61},
number = {4},
pages = {721--743},
doi = {10.1007/s10898-014-0156-4}
}
@article{Joseph-Duran2014,
author = {Joseph-Duran, B. and Jung, M. and Ocampo-Martinez, C. and Sager, S. and Cambrano, G.},
title = {{M}inimization of {S}ewage {N}etwork {O}verflow},
journal = {{W}ater {R}esources {M}anagement},
year = {2014},
volume = {28},
number = {1},
pages = {41--63},
doi = {10.1007/s11269-013-0468-z}
}
@phdthesis{Jung2013a,
author = {Jung, M.},
title = {{R}elaxations and {A}pproximations for {M}ixed-{I}nteger {O}ptimal {C}ontrol},
school = {University Heidelberg},
year = {2013},
url = {http://www.ub.uni-heidelberg.de/archiv/16036}
}
@article{Sager2013,
author = {Sager, S.},
title = {{S}ampling {D}ecisions in {O}ptimum {E}xperimental {D}esign in the {L}ight of {P}ontryagin's {M}aximum {P}rinciple},
journal = {{SIAM} Journal on Control and Optimization},
year = {2013},
volume = {51},
number = {4},
pages = {3181--3207},
url = {https://mathopt.de/publications/Sager2013.pdf}
}
@article{Sager2012a,
author = {Sager, S. and Bock, H.G. and Diehl, M.},
title = {{T}he {I}nteger {A}pproximation {E}rror in {M}ixed-{I}nteger {O}ptimal {C}ontrol},
journal = {{M}athematical {P}rogramming {A}},
year = {2012},
volume = {133},
number = {1--2},
pages = {1--23},
url = {https://mathopt.de/publications/Sager2012a.pdf}
}
@inproceedings{Sager2012b,
author = {Sager, S.},
title = {{A} benchmark library of mixed-integer optimal control problems},
booktitle = {{M}ixed {I}nteger {N}onlinear {P}rogramming},
publisher = {Springer},
year = {2012},
editor = {Lee, J. and Leyffer, S.},
pages = {631--670},
url = {https://mathopt.de/publications/Sager2012b.pdf}
}
@article{Sager2011a,
author = {Sager, S. and Jung, M. and Kirches, C.},
title = {{C}ombinatorial {I}ntegral {A}pproximation},
journal = {{M}athematical {M}ethods of {O}perations {R}esearch},
year = {2011},
volume = {73},
number = {3},
pages = {363--380},
url = {https://mathopt.de/publications/Sager2011a.pdf},
doi = {10.1007/s00186-011-0355-4}
}
@misc{Sager2011d,
author = {Sager, S.},
title = {{O}n the {I}ntegration of {O}ptimization {A}pproaches for {M}ixed-{I}nteger {N}onlinear {O}ptimal {C}ontrol},
year = {2011},
note = {Habilitation},
url = {https://mathopt.de/publications/Sager2011d.pdf}
}
@article{Sager2009b,
author = {Sager, S.},
title = {{R}eformulations and {A}lgorithms for the {O}ptimization of {S}witching {D}ecisions in {N}onlinear {O}ptimal {C}ontrol},
journal = {{J}ournal of {P}rocess {C}ontrol},
year = {2009},
volume = {19},
number = {8},
pages = {1238--1247},
url = {https://mathopt.de/publications/Sager2009b.pdf}
}
@book{Sager2005,
author = {Sager, S.},
title = {{N}umerical methods for mixed--integer optimal control problems},
publisher = {Der andere {V}erlag},
year = {2005},
address = {T\"onning, L\"ubeck, Marburg},
note = {ISBN 3-89959-416-9},
url = {https://mathopt.de/publications/Sager2005.pdf}
}