Open Journal of Mathematical Optimization

Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty
Hande Yaman1
1 ORSTAT, Faculty of Economics and Business KU Leuven, 3000 Leuven, Belgium
Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 4, 7 p.

In this paper, we consider a robust combinatorial optimization problem with uncertain weights and propose an uncertainty set that generalizes interval uncertainty by imposing lower and upper bounds on deviations of subsets of items. We prove that if the number of such subsets is fixed and the family of these subsets is laminar, then the robust combinatorial optimization problem can be solved by solving a fixed number of nominal problems. This result generalizes a previous similar result for the case where the family of these subsets is a partition of the set of items.

Received:
Accepted:
Revised after acceptance:
Published online:
DOI: 10.5802/ojmo.23
Keywords: robust combinatorial optimization, interval uncertainty, budgeted uncertainty, complexity
Hande Yaman 1

1 ORSTAT, Faculty of Economics and Business KU Leuven, 3000 Leuven, Belgium
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2023__4__A4_0,
     author = {Hande Yaman},
     title = {Short {Paper} - {A} {Note} on {Robust} {Combinatorial} {Optimization} with {Generalized} {Interval} {Uncertainty}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {4},
     pages = {1--7},
     publisher = {Universit\'e de Montpellier},
     volume = {4},
     year = {2023},
     doi = {10.5802/ojmo.23},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.23/}
}
TY  - JOUR
AU  - Hande Yaman
TI  - Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty
JO  - Open Journal of Mathematical Optimization
PY  - 2023
SP  - 1
EP  - 7
VL  - 4
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.23/
DO  - 10.5802/ojmo.23
LA  - en
ID  - OJMO_2023__4__A4_0
ER  - 
%0 Journal Article
%A Hande Yaman
%T Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty
%J Open Journal of Mathematical Optimization
%D 2023
%P 1-7
%V 4
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.23/
%R 10.5802/ojmo.23
%G en
%F OJMO_2023__4__A4_0
Hande Yaman. Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty. Open Journal of Mathematical Optimization, Volume 4 (2023), article  no. 4, 7 p. doi : 10.5802/ojmo.23. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.23/

[1] Ayşegül Altın; Hande Yaman; Mustafa Ç. Pınar A hybrid polyhedral uncertainty model for the robust network loading problem, Performance models and risk management in communications systems (Springer Optimization and Its Applications), Volume 46, Springer, 2011, pp. 157-172 | DOI | MR | Zbl

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

[3] Timothy C. Y. Chan; Zuo-Jun Max Shen; Auyon Siddiq Robust defibrillator deployment under cardiac arrest location uncertainty via row-and-column generation, Oper. Res., Volume 66 (2018) no. 2, pp. 358-379 | DOI | MR | Zbl

[4] Nick G. Duffield; Pawan Goyal; Albert Greenberg; Partho Mishra; Kadangode K Ramakrishnan; Jacobus E. van der Merive A flexible model for resource management in virtual private networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, ACM Press (1999), pp. 95-108

[5] J. Andrew Fingerhut; Subhash Suri; Jonathan S. Turner Designing least-cost nonblocking broadband networks, J. Algorithms, Volume 24 (1997) no. 2, pp. 287-309 | DOI | MR | Zbl

[6] Marc Goerigk; Stefan Lendl Robust combinatorial optimization with locally budgeted uncertainty, Open J. Math. Optim., Volume 2 (2021) no. 3, p. 18 | Numdam | MR | Zbl

[7] 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, Transp. Sci., Volume 50 (2016) no. 4, pp. 1239-1260 | DOI

[8] Chrysanthos E. Gounaris; Wolfram Wiesemann; Christodoulos A. Floudas The robust capacitated vehicle routing problem under demand uncertainty, Oper. Res., Volume 61 (2013) no. 3, pp. 677-693 | DOI | MR | Zbl

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

[10] Wolfram Wiesemann; Daniel Kuhn; Melvyn Sim Distributionally robust convex optimization, Oper. Res., Volume 62 (2014) no. 6, pp. 1358-1376 | DOI | MR | Zbl

Cited by Sources: