Optimization Online


Approximation Properties of Sum-Up Rounding in the Presence of Vanishing Constraints

Paul Manns (paul.manns***at***tu-bs.de)
Christian Kirches (c.kirches***at***tu-bs.de)
Felix Lenders (felix.lenders***at***iwr.uni-heidelberg.de)

Abstract: Approximation algorithms like sum-up rounding that allow to compute integer-valued approximations of the continuous controls in a weak$^*$ sense have attracted interest recently. They allow to approximate (optimal) feasible solutions of continuous relaxations of mixed-integer control problems (MIOCPs) with integer controls arbitrarily close. To this end, they use compactness properties of the underlying state equation, a feature that is tied to the infinite-dimensional vantage point. In this work, we consider a class of MIOCPs that are constrained by pointwise mixed state-control constraints. We show that a continuous relaxation that involves so-called vanishing constraints has beneficial properties for the described approximation methodology. Moreover, we complete recent work on a variant of the sum-up rounding algorithm for this problem class. In particular, we prove that the observed infeasibility of the produced integer-valued controls vanishes in an $L^\infty$-sense with respect to the considered relaxation. Moreover, we improve the bound on the control approximation error to a value that is asymptotically tight.

Keywords: Discrete approximations, error estimates, relaxations of mixed integer optimal control

Category 1: Combinatorial Optimization (Approximation Algorithms )

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

Category 3: Nonlinear Optimization (Systems governed by Differential Equations Optimization )


Download: [PDF]

Entry Submitted: 04/19/2018
Entry Accepted: 04/19/2018
Entry Last Modified: 03/15/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