Two-stage flexible-choice problems under uncertainty

Jurij Mihelic, Amine Mahjoub, Christophe Rapine and Borut Robic

European Journal of Operational Research, 2010, vol. 201, issue 2, 399-403

Abstract: A significant input-data uncertainty is often present in practical situations. One approach to coping with this uncertainty is to describe the uncertainty with scenarios. A scenario represents a potential realization of the important parameters of the problem. In this paper we apply a recent approach, called flexibility, to solving two-stage flexible-choice problems. The first stage represents the present, where a decision maker must plan ahead to make a decision to hedge against uncertainty in the second stage, which represents the uncertain future, and is described as a set of scenarios. When one of the future scenarios is realized, a decision maker is willing to pay some recourse cost to augment the earlier solution to be more suitable for the realized scenario. Since all of the future scenarios are known, it is reasonable to presume that their desired solutions are also known. Thus, the aim of a decision maker is to find a solution in the present that is as easy as possible to adapt to solutions in the future. In this paper we study the problem where feasible solutions of the first stage are all p-element subsets of some finite set, and the solutions of the second stage are fixed p-element subsets. We present computational complexity results and algorithms for two versions of the two-stage flexible-choice problem. We formally define both problems, i.e., the sum-flexibility problem and the max-flexibility problem. For the sum-flexibility problem we describe an exact polynomial-time algorithm for the 3-scenario version, and we show non-approximability for the 4-scenario version. For the max-flexibility problem we show that the 3-scenario version is -hard, but approximable within a constant performance guarantee. Additionally, we prove non-approximability for the 4-scenario version of the problem.

Keywords: Complexity; theory; Uncertainty; modeling; Scenarios; Combinatorial; optimization; Decision; analysis; Network; flows (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00164-7
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:201:y:2010:i:2:p:399-403

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 ().