4.4 Article

Radius of Robust Feasibility for Mixed-Integer Problems

期刊

INFORMS JOURNAL ON COMPUTING
卷 34, 期 1, 页码 243-261

出版社

INFORMS
DOI: 10.1287/ijoc.2020.1030

关键词

robust optimization; mixed-integer programming; uncertainty sets; robust feasibility

资金

  1. Bayerisches Staatsministerium fur Wirtschaft und Medien, Energie und Technologie, Energie Campus Nurnberg
  2. Deutsche Forschungsgemeinschaft [CRC TRR 154]

向作者/读者索取更多资源

This paper studies the radius of robust feasibility (RRF) for mixed-integer linear problems (MIP) and extends its application to various optimization problems and uncertainty sets. The authors provide methods for computing the RRF of MIPs and present a theoretical contribution by generalizing RRF to include safe variables and constraints.
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 and to include safe variables and constraints; that is, 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 and 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. Summary of Contribution: Robust optimization is an important field of operations research due to its capability of protecting optimization problems from data uncertainties that are usually defined via so-called uncertainty sets. Intensive research has been conducted in developing algorithmically tractable reformulations of the usually semi-infinite robust optimization problems. However, in applications it also important to construct appropriate uncertainty sets (i.e., prohibiting too conservative, intractable, or even infeasible robust optimization problems due to the choice of the uncertainty set). In doing so, it is useful to know themaximal size of a given uncertainty set such that a robust feasible solution still exists. In this paper, we study one notion of size: the radius of robust feasibility (RRF). We contribute on the theoretical side by generalizing the RRF to MIPs as well as to include safe variables and constraints (i.e., where uncertainties do not affect certain variables or constraints). This allows to apply the RRF tomany applications since safe variables and constraints exist inmost applications. We also provide firstmethods 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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.4
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据