IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v201y2010i2p399-403.html
   My bibliography  Save this article

Two-stage flexible-choice problems under uncertainty

Author

Listed:
  • Mihelic, Jurij
  • Mahjoub, Amine
  • Rapine, Christophe
  • Robic, Borut

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.

Suggested Citation

  • Mihelic, Jurij & Mahjoub, Amine & Rapine, Christophe & Robic, Borut, 2010. "Two-stage flexible-choice problems under uncertainty," European Journal of Operational Research, Elsevier, vol. 201(2), pages 399-403, March.
  • Handle: RePEc:eee:ejores:v:201:y:2010:i:2:p:399-403
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00164-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hennessy, David A., 1999. "Capacity choice in a two-stage problem under uncertainty," Economics Letters, Elsevier, vol. 65(2), pages 177-182, November.
    2. Averbakh, Igor & Berman, Oded, 2000. "Algorithms for the robust 1-center problem on a tree," European Journal of Operational Research, Elsevier, vol. 123(2), pages 292-302, June.
    3. Randeep Bhatia & Sudipto Guha & Samir Khuller & Yoram J. Sussmann, 1998. "Facility Location with Dynamic Distance Functions," Journal of Combinatorial Optimization, Springer, vol. 2(3), pages 199-217, September.
    4. Yin, Yafeng & Madanat, Samer M. & Lu, Xiao-Yun, 2009. "Robust improvement schemes for road networks under demand uncertainty," European Journal of Operational Research, Elsevier, vol. 198(2), pages 470-479, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jurij Mihelič & Borut Robič, 2010. "Flexible-attribute problems," Computational Optimization and Applications, Springer, vol. 47(3), pages 553-566, November.
    2. Yuya Higashikawa & Naoki Katoh, 2019. "A Survey on Facility Location Problems in Dynamic Flow Networks," The Review of Socionetwork Strategies, Springer, vol. 13(2), pages 163-208, October.
    3. de Ruiter, Frans, 2018. "Primal and dual approaches to adjustable robust optimization," Other publications TiSEM 4ce224f3-d9fc-4283-b5a6-4, Tilburg University, School of Economics and Management.
    4. Du, Muqing & Tan, Heqing & Chen, Anthony, 2021. "A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium models," European Journal of Operational Research, Elsevier, vol. 290(3), pages 982-999.
    5. Elnaz Miandoabchi & Reza Farahani & W. Szeto, 2012. "Bi-objective bimodal urban road network design using hybrid metaheuristics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(4), pages 583-621, December.
    6. Tan, Zhijia & Yang, Hai & Tan, Wei & Li, Zhichun, 2016. "Pareto-improving transportation network design and ownership regimes," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 292-309.
    7. Sun, Yanshuo & Schonfeld, Paul, 2015. "Stochastic capacity expansion models for airport facilities," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 1-18.
    8. Jingfeng Yang & Hai Wang & Jiangang Jin, 2023. "Optimization of Station-Skip in a Cyclic Express Subway Service," Networks and Spatial Economics, Springer, vol. 23(2), pages 445-468, June.
    9. Backe, Stian & Ahang, Mohammadreza & Tomasgard, Asgeir, 2021. "Stable stochastic capacity expansion with variable renewables: Comparing moment matching and stratified scenario generation sampling," Applied Energy, Elsevier, vol. 302(C).
    10. S Mudchanatongsuk & F Ordóñez & J Liu, 2008. "Robust solutions for network design under transportation cost and demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 652-662, May.
    11. Tu, Ningwen & Li, Zhi-Chun & Fu, Xiaowen & Lei, Zheng, 2020. "Airline network competition in inter-continental market," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    12. Li, Anna C.Y. & Nozick, Linda & Xu, Ningxiong & Davidson, Rachel, 2012. "Shelter location and transportation planning under hurricane conditions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(4), pages 715-729.
    13. Lu, Yahan & Yang, Lixing & Yang, Hai & Zhou, Housheng & Gao, Ziyou, 2023. "Robust collaborative passenger flow control on a congested metro line: A joint optimization with train timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 27-55.
    14. Wei Ding & Ke Qiu, 2018. "A quadratic time exact algorithm for continuous connected 2-facility location problem in trees," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1262-1298, November.
    15. Dimitris Bertsimas & Frans J. C. T. de Ruiter, 2016. "Duality in Two-Stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 500-511, August.
    16. Shen, Siqian & Chen, Zhihao, 2013. "Optimization models for differentiating quality of service levels in probabilistic network capacity design problems," Transportation Research Part B: Methodological, Elsevier, vol. 58(C), pages 71-91.
    17. Hua Wang & Xiaoning Zhang, 2017. "Game theoretical transportation network design among multiple regions," Annals of Operations Research, Springer, vol. 249(1), pages 97-117, February.
    18. Federico Rupi & Silvia Bernardi & Guido Rossi & Antonio Danesi, 2015. "The Evaluation of Road Network Vulnerability in Mountainous Areas: A Case Study," Networks and Spatial Economics, Springer, vol. 15(2), pages 397-411, June.
    19. Yanfang Zhang & Xiaojun Chen, 2014. "Regularizations for Stochastic Linear Variational Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 163(2), pages 460-481, November.
    20. Bell, Michael G.H. & Fonzone, Achille & Polyzoni, Chrisanthi, 2014. "Depot location in degradable transport networks," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 148-161.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:201:y:2010:i:2:p:399-403. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.