Optimization methods & software · 2014 · 32 citations · 16 references
Natural SciencesMathematicsAlgorithmsDiscrete MathematicsOptimizationCombinatorial OptimizationConstrained OptimizationDiscrete OptimizationInteger ProgrammingNonlinear ProgrammingOptimal ControlCombinatorial ConstraintsLagrangian RelaxationMixed-integer Linear ProgrammingMixed-integer Nonlinear ProgrammingMixed-integer OptimizationMixed-integer ProgrammingNonlinear Optimal ControlObjective Function Value
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.
16
The Traveling-Salesman Problem and Minimum Spanning Trees
Michael Held, Richard M. Karp · Operations Research · 1970 · 1.4K citations
Daniel B. Leineweber, Irene Bauer, Hans Georg Bock et al. · Computers & Chemical Engineering · 2003 · 377 citations
Natural Sciences, Computational Engineering, Optimization +8