Optimization Online


Globalized Robust Optimization with Gamma-Uncertainties

Andreas Bärmann(Andreas.Baermann***at***math.uni-erlangen.de)
Christina Büsing(buesing***at***math2.rwth-aachen.de)
Frauke Liers(Frauke.Liers***at***math.uni-erlangen.de)

Abstract: Globalized robust optimization has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection depending on the distance of the realized scenario from the predefined uncertainty set. In this work, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its usability for discrete optimization. We show that in this case, the generalized robust counterpart possesses algorithmically tractable reformulations for mixed-integer linear nominal problems. Under mild assumptions, we derive a reformulation which uses only slightly more variables and constraints than the standard robust counterpart under Gamma-uncertainty. For combinatorial problems, our globalized robust counterpart remains fixed-parameter tractable, although with a runtime exponential in Gamma. Furthermore,we showthat globalized robust optimization under scaling of the Gamma-uncertainty-sets is NP-hard already in simple cases. We support our theoretical findings by experimental results on the globalized robust versions of the minimum-spanning-tree, shortest-path and knapsack problems. It turns out that our algorithmically tractable reformulations are not more difficult to solve than the respective standard robust counterparts while globalized robustness is guaranteed. Moreover, they produce solutions which offer suitable protection against uncertainty while performing very well in the nominal objective function.

Keywords: Globalized Robust Optimization, Gamma-Uncertainties, Mixed-Integer Programming, Combinatorial Optimization

Category 1: Robust Optimization

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

Category 3: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 06/14/2019
Entry Accepted: 06/14/2019
Entry Last Modified: 06/14/2019

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