Two-Stage Robust Combinatorial Optimization with Priced Scenarios

Roman Rischke ()
Additional contact information
Roman Rischke: Technische Universität Berlin

A chapter in Operations Research Proceedings 2013, 2014, pp 377-382 from Springer

Abstract: Abstract Two-stage robust combinatorial optimization is an established methodology for handling combinatorial optimization problems with uncertain input. Without knowing the actual data, a partial solution needs to be fixed in the first stage which is then extended to a feasible solution in the second stage at higher cost once the data is revealed. The overall goal is to construct a solution that is feasible in all scenarios, i.e., robust against uncertainty, and minimizes the worst-case cost. Since considering all possible scenarios usually leads to a robust solution that is too conservative and too expensive, a central question is to decide on a subset of scenarios to be taken into account. Restricting the set of possible scenarios is a common approach, but this usually depends on subjective decision criteria like the willingness to take risks or the expectation on the future. We propose an alternative concept. Instead of restricting the set of scenarios we price all scenarios, which affects the objective function in such a way that we receive a certain scenario-dependent reward that reduces the overall cost. This leads to new two-stage robust optimization problems. We study complexity and devise approximation algorithms for such problems.

Keywords: Robust Combinatorial Optimization; Subjective Decision Criteria; Devise Approximation Algorithms; Worst-case Cost; Established Methodology (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-319-07001-8_51

Ordering information: This item can be ordered from
http://www.springer.com/9783319070018

DOI: 10.1007/978-3-319-07001-8_51

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().