• search hit 1 of 8
Back to Result List

Radius of Robust Feasibility for Mixed-Integer Problems

Submission Status:Published
  • 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. The approaches for the RRF in the literature are restricted to continuous optimization problems. We first analyze relations between the RRF of a MIP and its continuous linear (LP) relaxation. In particular, we derive conditions under which a MIP and its LP relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied to 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 RRF to MIPs as well as to include “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In the extended setting, we again analyze relations between the RRF for a MIP and its LP relaxation. Afterward, we present methods for computing the RRF of LPs as well as of MIPs with safe variables and constraints. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 for computing the RRF.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Frauke Liers, Lars Schewe, Johannes Thürauf
Publisher:Informs Journal on Computing
Document Type:Preprint
Date of Publication (online):2019/05/20
Date of first Publication:2019/05/20
Release Date:2019/05/20
Tag:Robust Optimization, Mixed-integer programming, Uncertainty sets, Robust feasibility
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Licence (German):License LogoCreative Commons - CC BY-NC-SA - Namensnennung - Nicht kommerziell - Weitergabe unter gleichen Bedingungen 4.0 International