On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909406590926848 |
|---|---|
| author | Grüne, Christoph Wulf, Lasse |
| author_facet | Grüne, Christoph Wulf, Lasse |
| contents | Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become $Σ^p_3$-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP $= Σ^p_3$ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, $p$-center, $p$-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, $k$-disjoint path ($k \geq 2$), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes $Σ^p_3$-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is $Σ^p_3$-complete. This reveals the insight that all the above problems are $Σ^p_3$-complete 'for the same reason'. Our result extends a recent framework by Grüne and Wulf. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18590 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy Grüne, Christoph Wulf, Lasse Computational Complexity Discrete Mathematics Optimization and Control F.2.2 Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become $Σ^p_3$-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP $= Σ^p_3$ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, $p$-center, $p$-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, $k$-disjoint path ($k \geq 2$), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes $Σ^p_3$-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is $Σ^p_3$-complete. This reveals the insight that all the above problems are $Σ^p_3$-complete 'for the same reason'. Our result extends a recent framework by Grüne and Wulf. |
| title | On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy |
| topic | Computational Complexity Discrete Mathematics Optimization and Control F.2.2 |
| url | https://arxiv.org/abs/2411.18590 |