We are interested in methods to solve mixed-integer nonlinear optimal control problems (MIOCPs) constrained by ordinary di erential equations and combinatorial constraints on some of the control functions. To solve these problems we use a rst discretize, then opti- mize approach to get a specially structured mixed-integer nonlinear program (MINLP). We decompose this MINLP into an NLP and an MILP, which is called the combinatorial integral approximation problem (CIAP). Previous results guarantee an integer gap for the MINLP depending on the objective function value of the CIAP. The focus of this study is the analysis of the CIAP and of a tailored branch and bound method. We link the huge computational gains compared to commercial MILP solvers to an analysis of subproblems on the branching tree. To this end we study properties of the Lagrangian of the CIAP. Special focus is given to special ordered set constraints that are present due to an outer convexi cation of the control problem. Also subproblems that arise by application of branch and bound schemes are of interest. We prove polynomial runtime of the algorithm for special cases and give numerical evidence for eciency by means of a numerical benchmark problem.
Citation
submitted to "Optimization Methods and Software", Address: Im Neuenheimer Feld 368, D-69120 Heidelberg, Date: February 2012