  


Combinatorial Integral Approximation Decompositions for MixedInteger Optimal Control
Clemens Zeile(clemens.zeileovgu.de) Abstract: Solving mixedinteger 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 mixedinteger 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 mixedinteger 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, Mixedinteger Non linear Programming, Mixedinteger 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 MixedInteger Optimal Control", MathOpt Work Group, Faculty of Mathematics, OttovonGuerickeUniversity Magdeburg, Germany, Submitted to Mathematical Programming Computations Download: [PDF] Entry Submitted: 02/16/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  