Optimization Online


Mixed-Integer Optimal Control Problems with switching costs: A shortest path approach

Felix Bestehorn (f.bestehorn***at***tu-bs.de)
Christoph Hansknecht (c.hansknecht***at***tu-bs.de)
Christian Kirches (c.kirches***at***tu-bs.de)
Paul Manns (paul.manns***at***tu-bs.de)

Abstract: We investigate an extension of Mixed-Integer Optimal Control Problems (MIOCPs) by adding switching costs, which enables the penalization of chattering and extends current modeling capabilities. The decomposition approach, consisting of solving a partial outer convexification to obtain a relaxed solution and using rounding schemes to obtain a discrete-valued control can still be applied, but the rounding turns out to be difficult in the presence of switching costs or switching constraints as the underlying problem is an Integer Program (IP). We therefore reformulate the rounding problem into a shortest path problem on a parameterized family of directed acyclic graphs (DAGs). Solving the shortest path problem then allows to minimize switching costs and still maintain approximability with respect to the tunable DAG parameter theta. We provide a proof of a runtime bound on equidistant rounding grids, where the bound is linear in time discretization granularity and polynomial in theta. The efficacy of our approach is demonstrated by a comparison with an integer programming approach on a benchmark problem.

Keywords: Optimal Control, Discrete approximations, Nonlinear Programming, Mixed-integer Programming, Combinatorics

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

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 02/14/2020
Entry Accepted: 02/14/2020
Entry Last Modified: 09/30/2020

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