Optimization Online


Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control

Clemens Zeile (clemens.zeile***at***ovgu.de)
Tobias Weber (tobias.weber***at***ovgu.de)
Sebastian Sager (sager***at***ovgu.de)

Abstract: Solving mixed-integer nonlinear programs (MINLPs) is hard in theory and practice. Decomposing the nonlinear and the integer part seems promising from a computational point of view. In general, however, no bounds on the objective value gap can be guaranteed and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal control problems with binary choices that switch over time. Here, a priori bounds were derived for a decomposition into one continuous nonlinear control problem and one mixed-integer linear program, the combinatorial integral approximation (CIA) problem. We generalize and extend the decomposition idea. First, we derive different de- compositions and analyze the implied a priori bounds. Second, we propose several strategies to generate promising candidate solutions for the binary control functions in the original problem. We present the extensions for problems constrained by ordinary differential equations. They are transferable in a straightforward way though to recently suggested variants for certain partial differential equations, for algebraic equations, for additional combinatorial constraints, and for discrete time problems. All algorithms and subproblems were implemented in AMPL for proof of concept. Numerical results show the improvement compared to standard CIA decomposition with respect to objective function value and compared to general purpose MINLP solvers with respect to runtime.

Keywords: Optimal control, Switched Dynamic Systems, Mixed-integer Non- linear Programming, Mixed-integer Linear Programming, Ordinary Differential Equations, Approximation methods and heuristics

Category 1: Nonlinear Optimization (Systems governed by Differential Equations Optimization )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Zeile, Clemens and Weber, Tobias and Sager, Sebastian. "Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control", MathOpt Work Group, Faculty of Mathematics, Otto-von-Guericke-University Magdeburg, Germany, Submitted to Mathematical Programming Computations

Download: [PDF]

Entry Submitted: 02/16/2018
Entry Accepted: 02/16/2018
Entry Last Modified: 12/13/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society