Mathematical Algorithmic Optimization - Otto-von-Guericke-University Magdeburg

 
 
 
 
 
 
 
 

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
Joseph-Duran, B., Jung, M., Ocampo-Martinez, C., Sager, S. & Cambrano, G. Minimization of Sewage Network Overflow 2014 Water Resources Management   article
 
BibTeX:
@article{Joseph-Duran2014,
  author = {B. Joseph-Duran and M. Jung and C. Ocampo-Martinez and S. Sager and G. Cambrano},
  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}
}
Jung, M. Relaxations and Approximations for Mixed-Integer Optimal Control 2013 School: University Heidelberg   phdthesis
preprint  
BibTeX:
@phdthesis{Jung2013a,
  author = {M. Jung},
  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}
}
Jung, M., Reinelt, G. & Sager, S. The Lagrangian Relaxation for the Combinatorial Integral Approximation Problem 2015 Optimization Methods and Software   article
 
BibTeX:
@article{Jung2015,
  author = {M. Jung and G. Reinelt and S. Sager},
  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}
}
Sager, S. A benchmark library of mixed-integer optimal control problems 2012 Mixed Integer Nonlinear Programming   inproceedings
preprint  
BibTeX:
@inproceedings{Sager2012b,
  author = {S. Sager},
  title = {{A} benchmark library of mixed-integer optimal control problems},
  booktitle = {{M}ixed {I}nteger {N}onlinear {P}rogramming},
  publisher = {Springer},
  year = {2012},
  editor = {J. Lee and S. Leyffer},
  pages = {631--670},
  url = {http://mathopt.de/PUBLICATIONS/Sager2012b.pdf}
}
Sager, S. Sampling Decisions in Optimum Experimental Design in the Light of Pontryagin's Maximum Principle 2013 SIAM Journal on Control and Optimization   article
preprint  
BibTeX:
@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 = {http://mathopt.de/PUBLICATIONS/Sager2013.pdf}
}
Sager, S. On the Integration of Optimization Approaches for Mixed-Integer Nonlinear Optimal Control 2011   misc
preprint  
BibTeX:
@misc{Sager2011d,
  author = {S. Sager},
  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 = {http://mathopt.de/PUBLICATIONS/Sager2011d.pdf}
}
Sager, S., Bock, H. & Diehl, M. The Integer Approximation Error in Mixed-Integer Optimal Control 2012 Mathematical Programming A   article
preprint  
BibTeX:
@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 = {http://mathopt.de/PUBLICATIONS/Sager2012a.pdf}
}
Sager, S., Jung, M. & Kirches, C. Combinatorial Integral Approximation 2011 Mathematical Methods of Operations Research   article DOI
preprint  
BibTeX:
@article{Sager2011a,
  author = {S. Sager and M. Jung and C. Kirches},
  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 = {http://mathopt.de/PUBLICATIONS/Sager2011a.pdf},
  doi = {http://dx.doi.org/10.1007/s00186-011-0355-4}
}

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

Last Modification: 2016-05-12 - Contact Person: Sebastian Sager - Impressum