Optimization Online


Combinatorial Integral Approximation

Sebastian Sager (sebastian.sager***at***iwr.uni-heidelberg.de)
Michael Jung (michael.jung***at***iwr.uni-heidelberg.de)
Christian Kirches (christian.kirches***at***iwr.uni-heidelberg.de)

Abstract: We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel approach that is based on a decomposition of the MINLP into a NLP and a MILP. We discuss the relation of the MILP solution to the MINLP solution and formulate bounds for the gap between the two, depending on Lipschitz constants and the control discretization grid size. The MILP solution can also be used for an efficient initialization of the MINLP solution process. The speedup of the solution of the MILP compared to the MINLP solution is considerable already for general purpose MILP solvers. We analyze the structure of the MILP that takes switching constraints into account and propose a tailored Branch and Bound strategy that outperforms Cplex and Gurobi on a numerical case study and hence further improves efficiency of our novel method.

Keywords: mixed-integer nonlinear programming, optimal control, switching constraints

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

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

Category 3: Infinite Dimensional Optimization (Distributed Control )

Citation: accepted by MMOR

Download: [PDF]

Entry Submitted: 05/07/2010
Entry Accepted: 05/07/2010
Entry Last Modified: 08/18/2010

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 Programming Society