Optimization Online


The Lagrangian Relaxation for the Combinatorial Integral Approximation Problem

Michael N. Jung(michael.jung***at***iwr.uni-heidelberg.de)
Sebastian Sager(sebastian.sager***at***iwr.uni-heidelberg.de)
Gerhard Reinelt(gerhard.reinelt***at***informatik.uni-heidelberg.de)

Abstract: 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.

Keywords: optimal control, MIOCP, integer programming, MILP, Lagrangian relaxation

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: submitted to "Optimization Methods and Software", Address: Im Neuenheimer Feld 368, D-69120 Heidelberg, Date: February 2012

Download: [PDF]

Entry Submitted: 02/13/2012
Entry Accepted: 02/13/2012
Entry Last Modified: 02/13/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society