Radius of Robust Feasibility for Mixed-Integer Problems

Weiterer Publikationstyp


Details zur Publikation

Autorinnen und Autoren: Liers F, Schewe L, Thürauf J
Jahr der Veröffentlichung: 2019
Sprache: Englisch


Abstract

For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. To the best of our knowledge, the approaches for the RRF presented in the literature are restricted to continuous optimization problems. In this work, we first analyze relations between the RRF of a MIP and its continuous linear programming relaxation. In particular, we derive conditions under which a MIP and its continuous relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied and computed for a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the concept of the RRF to MIPs including “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In this extended setting, we again analyze relations between the RRF for a MIP and its continuous relaxation. Afterward, we present methods for computing the RRF for continuous linear as well as mixed-integer problems with safe constraints and variables. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 library for the calculation of the RRF.


FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Schewe, Lars PD Dr.
Professur für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Thürauf, Johannes
Professur für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)


Zitierweisen

APA:
Liers, F., Schewe, L., & Thürauf, J. (2019). Radius of Robust Feasibility for Mixed-Integer Problems.

MLA:
Liers, Frauke, Lars Schewe, and Johannes Thürauf. Radius of Robust Feasibility for Mixed-Integer Problems. 2019.

BibTeX: 

Zuletzt aktualisiert 2019-20-05 um 16:53