Robust Combinatorial Optimization with Locally Budgeted Uncertainty
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 be...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2021-05-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/ |
| _version_ | 1811161334715252736 |
|---|---|
| author | Goerigk, Marc Lendl, Stefan |
| author_facet | Goerigk, Marc Lendl, Stefan |
| author_sort | Goerigk, Marc |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T06:12:39Z |
| format | Article |
| id | doaj.art-38c0eee2d5c0461483eb9cb5bbc624d0 |
| institution | Directory Open Access Journal |
| issn | 2777-5860 |
| language | English |
| last_indexed | 2024-04-10T06:12:39Z |
| publishDate | 2021-05-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj.art-38c0eee2d5c0461483eb9cb5bbc624d02023-03-02T11:40:12ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602021-05-01211810.5802/ojmo.510.5802/ojmo.5Robust Combinatorial Optimization with Locally Budgeted UncertaintyGoerigk, Marc0Lendl, Stefan1Network and Data Science Management, University of Siegen, Siegen, GermanyDepartment of Operations and Information Systems, University of Graz, Austria; Institute of Discrete Mathematics, Graz University of Technology, Graz, AustriaBudgeted 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/robust optimizationcombinatorial optimizationbudgeted uncertainty |
| spellingShingle | Goerigk, Marc Lendl, Stefan Robust Combinatorial Optimization with Locally Budgeted Uncertainty Open Journal of Mathematical Optimization robust optimization combinatorial optimization budgeted uncertainty |
| title | Robust Combinatorial Optimization with Locally Budgeted Uncertainty |
| title_full | Robust Combinatorial Optimization with Locally Budgeted Uncertainty |
| title_fullStr | Robust Combinatorial Optimization with Locally Budgeted Uncertainty |
| title_full_unstemmed | Robust Combinatorial Optimization with Locally Budgeted Uncertainty |
| title_short | Robust Combinatorial Optimization with Locally Budgeted Uncertainty |
| title_sort | robust combinatorial optimization with locally budgeted uncertainty |
| topic | robust optimization combinatorial optimization budgeted uncertainty |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.5/ |
| work_keys_str_mv | AT goerigkmarc robustcombinatorialoptimizationwithlocallybudgeteduncertainty AT lendlstefan robustcombinatorialoptimizationwithlocallybudgeteduncertainty |