On recoverable and two-stage robust selection problems with budgeted uncertainty

André Chassein, Marc Goerigk, Adam Kasperski and Paweł Zieliński

European Journal of Operational Research, 2018, vol. 265, issue 2, 423-436

Abstract: In this paper, the problem of selecting p out of n available items is discussed, such that their total cost is minimized. We assume that the item costs are not known exactly, but stem from a set of possible outcomes modeled through budgeted uncertainty sets, i.e., the interval uncertainty sets with an additional linear (budget) constraint, in their discrete and continuous variants. Robust recoverable and two-stage models of this selection problem are analyzed through an in-depth discussion of variables at their optimal values. Polynomial algorithms for both models under continuous budgeted uncertainty are proposed. In the case of discrete budgeted uncertainty, compact mixed integer formulations are constructed and some approximation algorithms are proposed. Polynomial combinatorial algorithms for the adversarial and incremental problems (the special cases of the considered robust models) under both discrete and continuous budgeted uncertainty are constructed.

Keywords: Combinatorial optimization; Robust optimization; Selection problem; Budgeted uncertainty; Two-stage robustness; Recoverable robustness (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717307440
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:265:y:2018:i:2:p:423-436

DOI: 10.1016/j.ejor.2017.08.013

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().