Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/323262 
Erscheinungsjahr: 
2024
Quellenangabe: 
[Journal:] OR Spectrum [ISSN:] 1436-6304 [Volume:] 47 [Issue:] 1 [Publisher:] Springer Berlin Heidelberg [Place:] Berlin/Heidelberg [Year:] 2024 [Pages:] 255-285
Verlag: 
Springer Berlin Heidelberg, Berlin/Heidelberg
Zusammenfassung: 
Abstract In robust combinatorial optimization, we would like to find a solution that performs well under all realizations of an uncertainty set of possible parameter values. How we model this uncertainty set has a decisive influence on the complexity of the corresponding robust problem. For this reason, budgeted uncertainty sets are often studied, as they enable us to decompose the robust problem into easier subproblems. We propose a variant of discrete budgeted uncertainty for cardinality-based constraints or objectives, where a weight vector is applied to the budget constraint. We show that while the adversarial problem can be solved in linear time, the robust problem becomes NP-hard and not approximable. We discuss different possibilities to model the robust problem and show experimentally that despite the hardness result, some models scale relatively well in the problem size.
Schlagwörter: 
Robust optimization
Combinatorial optimization
Budgeted uncertainty
Knapsack uncertainty
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version
Erscheint in der Sammlung:

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.