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.
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
Article
View Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control