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

An approximation framework for two-stage ambiguous stochastic integer programs under mean-MAD information

Author

Listed:
  • Postek, Krzysztof
  • Romeijnders, Ward
  • den Hertog, Dick
  • van der Vlerk, Maarten H.

Abstract

We consider two-stage recourse models in which only limited information is available on the probability distributions of the random parameters in the model. If all decision variables are continuous, then we are able to derive the worst-case and best-case probability distributions under the assumption that only the means and mean absolute deviations of the random parameters are known. Contrary to most existing results in the literature, these probability distributions are the same for every first-stage decision. The ambiguity set that we use in this paper also turns out to be particularly suitable for ambiguous recourse models involving integer decisions variables. For such problems, we develop a general approximation framework and derive error bounds for using these approximatons. We apply this approximation framework to mixed-ambiguous mixed-integer recourse models in which some of the probability distributions of the random parameters are known and others are ambiguous. To illustrate these results we carry out numerical experiments on a surgery block allocation problem.

Suggested Citation

  • Postek, Krzysztof & Romeijnders, Ward & den Hertog, Dick & van der Vlerk, Maarten H., 2019. "An approximation framework for two-stage ambiguous stochastic integer programs under mean-MAD information," European Journal of Operational Research, Elsevier, vol. 274(2), pages 432-444.
    • Handle: RePEc:eee:ejores:v:274:y:2019:i:2:p:432-444
    DOI: 10.1016/j.ejor.2018.10.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718308592
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.10.008?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Ward Romeijnders & David P. Morton & Maarten H. van der Vlerk, 2017. "Assessing the Quality of Convex Approximations for Two-Stage Totally Unimodular Integer Recourse Models," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 211-231, May.
    2. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    3. Dimitris Bertsimas & Angelos Georghiou, 2015. "Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization," Operations Research, INFORMS, vol. 63(3), pages 610-627, June.
    4. Brian T. Denton & Andrew J. Miller & Hari J. Balasubramanian & Todd R. Huschka, 2010. "Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty," Operations Research, INFORMS, vol. 58(4-part-1), pages 802-816, August.
    5. Grani A. Hanasusanto & Daniel Kuhn & Wolfram Wiesemann, 2015. "K -Adaptability in Two-Stage Robust Binary Programming," Operations Research, INFORMS, vol. 63(4), pages 877-891, August.
    6. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    7. Krzysztof Postek & Dick den Hertog, 2016. "Multistage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty Set," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 553-574, August.
    8. Aharon Ben-Tal & Eithan Hochman, 1976. "Stochastic Programs with Incomplete Information," Operations Research, INFORMS, vol. 24(2), pages 336-347, April.
    9. Wolfram Wiesemann & Daniel Kuhn & Melvyn Sim, 2014. "Distributionally Robust Convex Optimization," Operations Research, INFORMS, vol. 62(6), pages 1358-1376, December.
    10. Willem Klein Haneveld & Maarten van der Vlerk, 1999. "Stochastic integer programming:General models and algorithms," Annals of Operations Research, Springer, vol. 85(0), pages 39-57, January.
    11. Julia L. Higle & Suvrajeet Sen, 1991. "Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse," Mathematics of Operations Research, INFORMS, vol. 16(3), pages 650-669, August.
    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. Postek, Krzysztof & Romeijnders, Ward & den Hertog, Dick & van der Vlerk, Maartne H., 2016. "Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information," Other publications TiSEM a03f895f-b941-41a9-84e0-b, Tilburg University, School of Economics and Management.
    2. Postek, Krzysztof & Romeijnders, Ward & den Hertog, Dick & van der Vlerk, Maartne H., 2016. "Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information," Discussion Paper 2016-039, Tilburg University, Center for Economic Research.
    3. Sergey S. Ketkov, 2023. "On the Multistage Shortest Path Problem Under Distributional Uncertainty," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 277-308, April.
    4. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    5. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2019. "Robust Dual Dynamic Programming," Operations Research, INFORMS, vol. 67(3), pages 813-830, May.
    6. Ward Romeijnders & David P. Morton & Maarten H. van der Vlerk, 2017. "Assessing the Quality of Convex Approximations for Two-Stage Totally Unimodular Integer Recourse Models," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 211-231, May.
    7. Wang, Yu & Zhang, Yu & Tang, Jiafu, 2019. "A distributionally robust optimization approach for surgery block allocation," European Journal of Operational Research, Elsevier, vol. 273(2), pages 740-753.
    8. Feng, Wei & Feng, Yiping & Zhang, Qi, 2021. "Multistage robust mixed-integer optimization under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 294(2), pages 460-475.
    9. Yu Wang & Yu Zhang & Minglong Zhou & Jiafu Tang, 2023. "Feature‐driven robust surgery scheduling," Production and Operations Management, Production and Operations Management Society, vol. 32(6), pages 1921-1938, June.
    10. Postek, Krzysztof & Ben-Tal, A. & den Hertog, Dick & Melenberg, Bertrand, 2015. "Exact Robust Counterparts of Ambiguous Stochastic Constraints Under Mean and Dispersion Information," Other publications TiSEM d718e419-a375-4707-b206-e, Tilburg University, School of Economics and Management.
    11. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    12. Vincent Tsz Fai Chow & Zheng Cui & Daniel Zhuoyu Long, 2022. "Target-Oriented Distributionally Robust Optimization and Its Applications to Surgery Allocation," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2058-2072, July.
    13. Anirudh Subramanyam & Frank Mufalli & José M. Lí?nez-Aguirre & Jose M. Pinto & Chrysanthos E. Gounaris, 2021. "Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty," Operations Research, INFORMS, vol. 69(1), pages 30-60, January.
    14. Farough Motamed Nasab & Zukui Li, 2023. "Multistage Adaptive Robust Binary Optimization: Uncertainty Set Lifting versus Partitioning through Breakpoints Optimization," Mathematics, MDPI, vol. 11(18), pages 1-24, September.
    15. Postek, Krzysztof & Ben-Tal, A. & den Hertog, Dick & Melenberg, Bertrand, 2015. "Exact Robust Counterparts of Ambiguous Stochastic Constraints Under Mean and Dispersion Information," Discussion Paper 2015-030, Tilburg University, Center for Economic Research.
    16. Weijun Xie & Shabbir Ahmed, 2018. "Distributionally robust simple integer recourse," Computational Management Science, Springer, vol. 15(3), pages 351-367, October.
    17. Christoph Buchheim & Jannis Kurtz, 2018. "Robust combinatorial optimization under convex and discrete cost uncertainty," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 211-238, September.
    18. Omar El Housni & Vineet Goyal, 2021. "On the Optimality of Affine Policies for Budgeted Uncertainty Sets," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 674-711, May.
    19. Lu, Mengshi & Nakao, Hideaki & Shen, Siqian & Zhao, Lin, 2021. "Non-profit resource allocation and service scheduling with cross-subsidization and uncertain resource consumptions," Omega, Elsevier, vol. 99(C).
    20. Amir Ardestani-Jaafari & Erick Delage, 2016. "Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems," Operations Research, INFORMS, vol. 64(2), pages 474-494, April.

    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:274:y:2019:i:2:p:432-444. 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.