Globalized Robust Optimization with Gamma-Uncertainties

Other publication type


Publication Details

Author(s): Bärmann A, Büsing C, Liers F
Publication year: 2019
Language: English


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.


FAU Authors / FAU Editors

Bärmann, Andreas Dr.
Economics - Discrete Optimization - Mathematics (EDOM)
Liers-Bergmann, Frauke Prof. Dr.
Professur für Diskrete Optimierung in den Ingenieurwissenschaften


External institutions
Rheinisch-Westfälische Technische Hochschule (RWTH) Aachen


How to cite

APA:
Bärmann, A., Büsing, C., & Liers, F. (2019). Globalized Robust Optimization with Gamma-Uncertainties.

MLA:
Bärmann, Andreas, Christina Büsing, and Frauke Liers. Globalized Robust Optimization with Gamma-Uncertainties. 2019.

BibTeX: 

Last updated on 2019-14-06 at 15:51