IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v13y2016i3d10.1007_s10287-016-0254-5.html
   My bibliography  Save this article

Monotonic bounds in multistage mixed-integer stochastic programming

Author

Listed:
  • Francesca Maggioni

    (Bergamo University)

  • Elisabetta Allevi

    (Brescia University)

  • Marida Bertocchi

    (Bergamo University)

Abstract

Multistage stochastic programs bring computational complexity which may increase exponentially with the size of the scenario tree in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal value are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. The computational complexity of the proposed lower and upper bounds is discussed and an algorithmic procedure to use them is provided. Numerical results on a real case transportation problem are presented.

Suggested Citation

  • Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2016. "Monotonic bounds in multistage mixed-integer stochastic programming," Computational Management Science, Springer, vol. 13(3), pages 423-457, July.
    • Handle: RePEc:spr:comgts:v:13:y:2016:i:3:d:10.1007_s10287-016-0254-5
    DOI: 10.1007/s10287-016-0254-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-016-0254-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10287-016-0254-5?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. M. Avriel & A. C. Williams, 1970. "The Value of Information and Stochastic Programming," Operations Research, INFORMS, vol. 18(5), pages 947-954, October.
    2. C. C. Huang & I. Vertinsky & W. T. Ziemba, 1977. "Sharp Bounds on the Value of Perfect Information," Operations Research, INFORMS, vol. 25(1), pages 128-139, February.
    3. Laureano Escudero & Araceli Garín & María Merino & Gloria Pérez, 2007. "The value of the stochastic solution in multistage problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 48-64, July.
    4. C. C. Huang & W. T. Ziemba & A. Ben-Tal, 1977. "Bounds on the Expectation of a Convex Function of a Random Variable: With Applications to Stochastic Programming," Operations Research, INFORMS, vol. 25(2), pages 315-325, April.
    5. Maarten Vlerk, 2010. "Convex approximations for a class of mixed-integer recourse models," Annals of Operations Research, Springer, vol. 177(1), pages 139-150, June.
    6. Karl Frauendorfer, 1988. "Solving SLP Recourse Problems with Arbitrary Multivariate Distributions---The Dependent Case," Mathematics of Operations Research, INFORMS, vol. 13(3), pages 377-394, August.
    7. Albert Madansky, 1960. "Inequalities for Stochastic Linear Programming Problems," Management Science, INFORMS, vol. 6(2), pages 197-204, January.
    8. Francesca Maggioni & Stein Wallace, 2012. "Analyzing the quality of the expected value solution in stochastic programming," Annals of Operations Research, Springer, vol. 200(1), pages 37-54, November.
    9. Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2014. "Bounds in Multistage Linear Stochastic Programming," Journal of Optimization Theory and Applications, Springer, vol. 163(1), pages 200-229, October.
    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. Daniel Kuhn, 2009. "An Information-Based Approximation Scheme for Stochastic Optimization Problems in Continuous Time," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 428-444, May.
    12. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
    2. Francesca Maggioni & Matteo Cagnolari & Luca Bertazzi, 2019. "The value of the right distribution in stochastic programming with application to a Newsvendor problem," Computational Management Science, Springer, vol. 16(4), pages 739-758, October.
    3. Ilke Bakir & Natashia Boland & Brian Dandurand & Alan Erera, 2020. "Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 145-163, January.
    4. Mahmutoğulları, Ali İrfan & Çavuş, Özlem & Aktürk, M. Selim, 2018. "Bounds on risk-averse mixed-integer multi-stage stochastic programming problems with mean-CVaR," European Journal of Operational Research, Elsevier, vol. 266(2), pages 595-608.
    5. Bomze, Immanuel M. & Gabl, Markus & Maggioni, Francesca & Pflug, Georg Ch., 2022. "Two-stage stochastic standard quadratic optimization," European Journal of Operational Research, Elsevier, vol. 299(1), pages 21-34.
    6. Francesca Maggioni & Elisabetta Allevi & Asgeir Tomasgard, 2020. "Bounds in multi-horizon stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 605-625, September.
    7. Kevin Ryan & Shabbir Ahmed & Santanu S. Dey & Deepak Rajan & Amelia Musselman & Jean-Paul Watson, 2020. "Optimization-Driven Scenario Grouping," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 805-821, July.
    8. Gambella, Claudio & Maggioni, Francesca & Vigo, Daniele, 2019. "A stochastic programming model for a tactical solid waste management problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 684-694.
    9. Ching-Hui Tang, 2018. "Two-stage stochastic modeling of transportation outsourcing plans for transshipment centers," 4OR, Springer, vol. 16(1), pages 67-94, March.
    10. Cavagnini, Rossana & Bertazzi, Luca & Maggioni, Francesca, 2022. "A rolling horizon approach for a multi-stage stochastic fixed-charge transportation problem with transshipment," European Journal of Operational Research, Elsevier, vol. 301(3), pages 912-922.
    11. Audrius Kabašinskas & Francesca Maggioni & Kristina Šutienė & Eimutis Valakevičius, 2019. "A multistage risk-averse stochastic programming model for personal savings accrual: the evidence from Lithuania," Annals of Operations Research, Springer, vol. 279(1), pages 43-70, August.
    12. İ. Esra Büyüktahtakın, 2022. "Stage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programs," Annals of Operations Research, Springer, vol. 309(1), pages 1-35, February.
    13. Giovanni Pantuso & Trine K. Boomsma, 2020. "On the number of stages in multistage stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 581-603, September.
    14. Francesca Maggioni & Florian A. Potra & Marida Bertocchi, 2017. "A scenario-based framework for supply planning under uncertainty: stochastic programming versus robust optimization approaches," Computational Management Science, Springer, vol. 14(1), pages 5-44, January.

    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. Francesca Maggioni & Elisabetta Allevi & Asgeir Tomasgard, 2020. "Bounds in multi-horizon stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 605-625, September.
    2. Bomze, Immanuel M. & Gabl, Markus & Maggioni, Francesca & Pflug, Georg Ch., 2022. "Two-stage stochastic standard quadratic optimization," European Journal of Operational Research, Elsevier, vol. 299(1), pages 21-34.
    3. Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2014. "Bounds in Multistage Linear Stochastic Programming," Journal of Optimization Theory and Applications, Springer, vol. 163(1), pages 200-229, October.
    4. Giovanni Pantuso & Trine K. Boomsma, 2020. "On the number of stages in multistage stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 581-603, September.
    5. Douglas Alem & Pedro Munari & Marcos Arenales & Paulo Ferreira, 2010. "On the cutting stock problem under stochastic demand," Annals of Operations Research, Springer, vol. 179(1), pages 169-186, September.
    6. İ. Esra Büyüktahtakın, 2022. "Stage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programs," Annals of Operations Research, Springer, vol. 309(1), pages 1-35, February.
    7. Steftcho P. Dokov & David P. Morton, 2005. "Second-Order Lower Bounds on the Expectation of a Convex Function," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 662-677, August.
    8. Ilke Bakir & Natashia Boland & Brian Dandurand & Alan Erera, 2020. "Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 145-163, January.
    9. D. Kuhn, 2009. "Convergent Bounds for Stochastic Programs with Expected Value Constraints," Journal of Optimization Theory and Applications, Springer, vol. 141(3), pages 597-618, June.
    10. Francesca Maggioni & Matteo Cagnolari & Luca Bertazzi, 2019. "The value of the right distribution in stochastic programming with application to a Newsvendor problem," Computational Management Science, Springer, vol. 16(4), pages 739-758, October.
    11. 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.
    12. Meersman, Tine & Maenhout, Broos & Van Herck, Koen, 2023. "A nested Benders decomposition-based algorithm to solve the three-stage stochastic optimisation problem modeling population-based breast cancer screening," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1273-1293.
    13. Marcio Costa Santos & Michael Poss & Dritan Nace, 2018. "A perfect information lower bound for robust lot-sizing problems," Annals of Operations Research, Springer, vol. 271(2), pages 887-913, December.
    14. Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
    15. Audrius Kabašinskas & Francesca Maggioni & Kristina Šutienė & Eimutis Valakevičius, 2019. "A multistage risk-averse stochastic programming model for personal savings accrual: the evidence from Lithuania," Annals of Operations Research, Springer, vol. 279(1), pages 43-70, August.
    16. Gambella, Claudio & Maggioni, Francesca & Vigo, Daniele, 2019. "A stochastic programming model for a tactical solid waste management problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 684-694.
    17. Ching-Hui Tang, 2018. "Two-stage stochastic modeling of transportation outsourcing plans for transshipment centers," 4OR, Springer, vol. 16(1), pages 67-94, March.
    18. Munoz, F.D. & Hobbs, B.F. & Watson, J.-P., 2016. "New bounding and decomposition approaches for MILP investment problems: Multi-area transmission and generation planning under policy constraints," European Journal of Operational Research, Elsevier, vol. 248(3), pages 888-898.
    19. Lulli, Guglielmo & Sen, Suvrajeet, 2006. "A heuristic procedure for stochastic integer programs with complete recourse," European Journal of Operational Research, Elsevier, vol. 171(3), pages 879-890, June.
    20. Osman Y. Özaltın & Oleg A. Prokopyev & Andrew J. Schaefer & Mark S. Roberts, 2011. "Optimizing the Societal Benefits of the Annual Influenza Vaccine: A Stochastic Programming Approach," Operations Research, INFORMS, vol. 59(5), pages 1131-1143, October.

    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:spr:comgts:v:13:y:2016:i:3:d:10.1007_s10287-016-0254-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.