The Lagrangian relaxation for the combinatorial integral approximation problem

We are interested in methods to solve mixed-integer nonlinear optimal control problems constrained by ordinary differential equations and combinatorial constraints on some of the control functions. To solve these problems we use a first discretize, then optimize approach to get a specially structured mixed-integer nonlinear program (MINLP). We decompose this MINLP into a nonlinear program (NLP) and a mixed-integer linear program (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 state-of-the-art MILP solvers to an analysis of subproblems on the branching tree. To this end we study properties of the Lagrangian relaxation of the CIAP. Special focus is given to special ordered set constraints that are present due to an outer convexification of the control problem. Also subproblems that arise by the application of branch-and-bound schemes are of interest. We prove polynomial runtime of the algorithm for special cases and give numerical evidence for efficiency by means of a numerical benchmark problem.