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.
Accepté le :
Accepté après révision le :
Publié le :
Yaman, Hande 1
CC-BY 4.0
@article{OJMO_2023__4__A4_0,
author = {Yaman, Hande},
title = {Short {Paper} - {A} {Note} on {Robust} {Combinatorial} {Optimization} with {Generalized} {Interval} {Uncertainty}},
journal = {Open Journal of Mathematical Optimization},
eid = {4},
pages = {1--7},
year = {2023},
publisher = {Universit\'e de Montpellier},
volume = {4},
doi = {10.5802/ojmo.23},
language = {en},
url = {https://www.numdam.org/articles/10.5802/ojmo.23/}
}
TY - JOUR AU - Yaman, Hande 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://www.numdam.org/articles/10.5802/ojmo.23/ DO - 10.5802/ojmo.23 LA - en ID - OJMO_2023__4__A4_0 ER -
%0 Journal Article %A Yaman, Hande %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://www.numdam.org/articles/10.5802/ojmo.23/ %R 10.5802/ojmo.23 %G en %F OJMO_2023__4__A4_0
Yaman, Hande. Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty. Open Journal of Mathematical Optimization, Tome 4 (2023), article no. 4, 7 p.. doi: 10.5802/ojmo.23
[1] 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] Robust discrete optimization and network flows, Math. Program., Volume 98 (2003) no. 1, pp. 49-71 | Zbl | DOI | MR
[3] 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] 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] Designing least-cost nonblocking broadband networks, J. Algorithms, Volume 24 (1997) no. 2, pp. 287-309 | DOI | MR | Zbl
[6] Robust combinatorial optimization with locally budgeted uncertainty, Open J. Math. Optim., Volume 2 (2021) no. 3, p. 18 | Zbl | MR | Numdam
[7] An adaptive memory programming framework for the robust capacitated vehicle routing problem, Transp. Sci., Volume 50 (2016) no. 4, pp. 1239-1260 | DOI
[8] The robust capacitated vehicle routing problem under demand uncertainty, Oper. Res., Volume 61 (2013) no. 3, pp. 677-693 | DOI | MR | Zbl
[9] Robust combinatorial optimization with knapsack uncertainty, Discrete Optim., Volume 27 (2018), pp. 88-102 | DOI | MR | Zbl
[10] Distributionally robust convex optimization, Oper. Res., Volume 62 (2014) no. 6, pp. 1358-1376 | DOI | MR | Zbl
Cité par Sources :
