Open Journal of Mathematical Optimization

Robust Combinatorial Optimization with Locally Budgeted Uncertainty
Marc Goerigk1; Stefan Lendl2, 3
1 Network and Data Science Management, University of Siegen, Siegen, Germany
2 Department of Operations and Information Systems, University of Graz, Austria
3 Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria
Open Journal of Mathematical Optimization, Volume 2 (2021), article no. 3, 18 p.

Budgeted uncertainty sets have been established as a major influence on uncertainty modeling for robust optimization problems. A drawback of such sets is that the budget constraint only restricts the global amount of cost increase that can be distributed by an adversary. Local restrictions, while being important for many applications, cannot be modeled this way.

We introduce a new variant of budgeted uncertainty sets, called locally budgeted uncertainty. In this setting, the uncertain parameters are partitioned, such that a classic budgeted uncertainty set applies to each part of the partition, called region.

In a theoretical analysis, we show that the robust counterpart of such problems for a constant number of regions remains solvable in polynomial time, if the underlying nominal problem can be solved in polynomial time as well. If the number of regions is unbounded, we show that the robust selection problem remains solvable in polynomial time, while also providing hardness results for other combinatorial problems.

In computational experiments using both random and real-world data, we show that using locally budgeted uncertainty sets can have considerable advantages over classic budgeted uncertainty sets.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.5
Keywords: robust optimization, combinatorial optimization, budgeted uncertainty
Marc Goerigk 1; Stefan Lendl 2, 3

1 Network and Data Science Management, University of Siegen, Siegen, Germany
2 Department of Operations and Information Systems, University of Graz, Austria
3 Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2021__2__A3_0,
     author = {Marc Goerigk and Stefan Lendl},
     title = {Robust {Combinatorial} {Optimization} with {Locally} {Budgeted} {Uncertainty}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {3},
     pages = {1--18},
     publisher = {Universit\'e de Montpellier},
     volume = {2},
     year = {2021},
     doi = {10.5802/ojmo.5},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/}
}
TY  - JOUR
AU  - Marc Goerigk
AU  - Stefan Lendl
TI  - Robust Combinatorial Optimization with Locally Budgeted Uncertainty
JO  - Open Journal of Mathematical Optimization
PY  - 2021
SP  - 1
EP  - 18
VL  - 2
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/
DO  - 10.5802/ojmo.5
LA  - en
ID  - OJMO_2021__2__A3_0
ER  - 
%0 Journal Article
%A Marc Goerigk
%A Stefan Lendl
%T Robust Combinatorial Optimization with Locally Budgeted Uncertainty
%J Open Journal of Mathematical Optimization
%D 2021
%P 1-18
%V 2
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/
%R 10.5802/ojmo.5
%G en
%F OJMO_2021__2__A3_0
Marc Goerigk; Stefan Lendl. Robust Combinatorial Optimization with Locally Budgeted Uncertainty. Open Journal of Mathematical Optimization, Volume 2 (2021), article  no. 3, 18 p. doi : 10.5802/ojmo.5. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/

[1] Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten Min–max and min–max regret versions of combinatorial optimization problems: A survey, Eur. J. Oper. Res., Volume 197 (2009) no. 2, pp. 427-438 | DOI | MR | Zbl

[2] Paola Alimonti; Viggo Kann Some APX-completeness results for cubic graphs, Theor. Comput. Sci., Volume 237 (2000) no. 1-2, pp. 123-134 | DOI | MR | Zbl

[3] Artur Alves Pessoa; Luigi Di Puglia Pugliese; Francesca Guerriero; Michael Poss Robust constrained shortest path problems under budgeted uncertainty, Networks, Volume 66 (2015) no. 2, pp. 98-111 | DOI | MR | Zbl

[4] Dimitris Bertsimas; Vishal Gupta; Nathan Kallus Data-driven robust optimization, Math. Program., Volume 167 (2018) no. 2, pp. 235-292 | DOI | MR | Zbl

[5] Dimitris Bertsimas; Melvyn Sim Robust discrete optimization and network flows, Math. Program., Volume 98 (2003) no. 1, pp. 49-71 | DOI | MR | Zbl

[6] Dimitris Bertsimas; Melvyn Sim The price of robustness, Oper. Res., Volume 52 (2004) no. 1, pp. 35-53 | DOI | MR | Zbl

[7] Marin Bougeret; Artur Alves Pessoa; Michael Poss Robust scheduling with budgeted uncertainty, Discrete Appl. Math., Volume 261 (2019), pp. 93-107 | DOI | MR | Zbl

[8] Christina Büsing; Fabio D’andreagiovanni New results about multi-band uncertainty in robust optimization, International Symposium on Experimental Algorithms (2012), pp. 63-74 | DOI | Zbl

[9] André Chassein; Trivikram Dokka; Marc Goerigk Algorithms and uncertainty sets for data-driven robust shortest path problems, Eur. J. Oper. Res., Volume 274 (2019) no. 2, pp. 671-686 | DOI | MR | Zbl

[10] André Chassein; Marc Goerigk; Adam Kasperski; Paweł Zieliński On recoverable and two-stage robust selection problems with budgeted uncertainty, Eur. J. Oper. Res., Volume 265 (2018) no. 2, pp. 423-436 | DOI | MR | Zbl

[11] André Chassein; Marc Goerigk; Jannis Kurtz; Michael Poss Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty, Eur. J. Oper. Res., Volume 279 (2019) no. 2, pp. 308-319 | DOI | MR | Zbl

[12] Vladimir G. Deineko; Gerhard J. Woeginger Complexity and in-approximability of a selection problem in robust optimization, 4OR, Volume 11 (2013) no. 3, pp. 249-252 | DOI | MR | Zbl

[13] Thomas Erlebach; Hans Kellerer; Ulrich Pferschy Approximating multiobjective knapsack problems, Manage. Sci., Volume 48 (2002) no. 12, pp. 1603-1612 | DOI | Zbl

[14] Michael R. Garey; David S. Johnson Computers and intractability, A Series of Books in the mathematical Sciences, 174, W. H. Freeman and Company, 1979 | Zbl

[15] Georgii V. Gens; Eugenii V. Levner Computational complexity of approximation algorithms for combinatorial problems, International Symposium on Mathematical Foundations of Computer Science (1979), pp. 292-300 | Zbl

[16] Marc Goerigk; Stefan Lendl; Lasse Wulf Recoverable Robust Representatives Selection Problems with Discrete Budgeted Uncertainty (2020) (https://arxiv.org/abs/2008.12727)

[17] Chrysanthos E. Gounaris; Panagiotis P. Repoussis; Christos D. Tarantilis; Wolfram Wiesemann; Christodoulos A. Floudas An adaptive memory programming framework for the robust capacitated vehicle routing problem, Transportation Science, Volume 50 (2016) no. 4, pp. 1239-1260 | DOI

[18] Christoph Hansknecht; Alexander Richter; Sebastian Stiller Fast robust shortest path computations, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) (2018)

[19] Adam Kasperski; Paweł Zieliński Robust discrete optimization under discrete and interval uncertainty: A survey, Robustness analysis in decision aiding, optimization, and analytics, Springer, 2016, pp. 113-143 | DOI | Zbl

[20] Hans Kellerer; Ulrich Pferschy; David Pisinger Knapsack Problems, Springer, 2004 | Zbl

[21] Panos Kouvelis; Gang Yu Robust discrete optimization and its applications, 14, Springer, 2013 | Zbl

[22] Michael Poss Robust combinatorial optimization with variable budgeted uncertainty, 4OR, Volume 11 (2013) no. 1, pp. 75-92 | DOI | MR | Zbl

[23] Michael Poss Robust combinatorial optimization with knapsack uncertainty, Discrete Optimization, Volume 27 (2018), pp. 88-102 | DOI | MR | Zbl

[24] Rishi Saket; Maxim Sviridenko New and improved bounds for the minimum set cover problem, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, Springer, 2012, pp. 288-300 | DOI | Zbl

[25] Gerhard J. Woeginger Exact algorithms for NP-hard problems: A survey, Combinatorial optimization – Eureka, you shrink! (Lecture Notes in Computer Science), Volume 2570, Springer, 2003, pp. 185-207 | DOI | MR | Zbl

Cited by Sources: