Projects per year
Abstract
Recoverable robust optimization is a multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We analyze this approach for a class of selection problems. The aim is to choose a fixed number of items from several disjoint sets, such that the worst-case costs after taking a recovery action are as small as possible. The uncertainty is modeled as a discrete budgeted set, where the adversary can increase the costs of a fixed number of items. While special cases of this problem have been studied before, its complexity has remained open. In this work we make several contributions towards closing this gap. We show that the problem is NP-hard and identify a special case that remains solvable in polynomial time. We provide a compact mixed-integer programming formulation and two additional extended formulations. Finally, computational results are provided that compare the efficiency of different exact solution approaches.
Original language | English |
---|---|
Pages (from-to) | 567-580 |
Number of pages | 14 |
Journal | European Journal of Operational Research |
Volume | 303 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Dec 2022 |
Keywords
- Robustness and sensitivity analysis
- Robust optimization
- Discrete budgeted uncertainty
- Combinatorial optimization
- Selection problems
ASJC Scopus subject areas
- Information Systems and Management
- General Computer Science
- Industrial and Manufacturing Engineering
- Modelling and Simulation
- Management Science and Operations Research
Fingerprint
Dive into the research topics of 'Recoverable robust representatives selection problems with discrete budgeted uncertainty'. Together they form a unique fingerprint.Projects
- 1 Active
-
Doctoral Program: Discrete Mathematics
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Project: Research project