Globalized Robust Optimization with Gamma-Uncertainties

Weiterer Publikationstyp

Details zur Publikation

Autorinnen und Autoren: Bärmann A, Büsing C, Liers F
Jahr der Veröffentlichung: 2019
Sprache: Englisch


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-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Bärmann, Andreas Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

Rheinisch-Westfälische Technische Hochschule (RWTH) Aachen


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

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


Zuletzt aktualisiert 2019-14-06 um 15:51