The robust selection problem with information discovery
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917884310061056 |
|---|---|
| author | Chen, Xiaoyu Goerigk, Marc Poss, Michael |
| author_facet | Chen, Xiaoyu Goerigk, Marc Poss, Michael |
| contents | We explore a multiple-stage variant of the min-max robust selection problem with budgeted uncertainty that includes queries. First, one queries a subset of items and gets the exact values of their uncertain parameters. Given this information, one can then choose the set of items to be selected, still facing uncertainty on the unobserved parameters. In this paper, we study two specific variants of this problem. The first variant considers objective uncertainty and focuses on selecting a single item. The second variant considers constraint uncertainty instead, which means that some selected items may fail. We show that both problems are NP-hard in general. We also propose polynomial-time algorithms for special cases of the sets of items that can be queried. For the problem with constraint uncertainty, we also show how the objective function can be expressed as a linear program, leading to a mixed-integer linear programming reformulation for the general case. We illustrate the performance of this formulation using numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02510 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The robust selection problem with information discovery Chen, Xiaoyu Goerigk, Marc Poss, Michael Optimization and Control We explore a multiple-stage variant of the min-max robust selection problem with budgeted uncertainty that includes queries. First, one queries a subset of items and gets the exact values of their uncertain parameters. Given this information, one can then choose the set of items to be selected, still facing uncertainty on the unobserved parameters. In this paper, we study two specific variants of this problem. The first variant considers objective uncertainty and focuses on selecting a single item. The second variant considers constraint uncertainty instead, which means that some selected items may fail. We show that both problems are NP-hard in general. We also propose polynomial-time algorithms for special cases of the sets of items that can be queried. For the problem with constraint uncertainty, we also show how the objective function can be expressed as a linear program, leading to a mixed-integer linear programming reformulation for the general case. We illustrate the performance of this formulation using numerical experiments. |
| title | The robust selection problem with information discovery |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.02510 |