IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v70y2017icp31-42.html
   My bibliography  Save this article

Two-stage stochastic mixed-integer linear programming: The conditional scenario approach

Author

Listed:
  • Beltran-Royo, C.

Abstract

In this paper we consider the two-stage stochastic mixed-integer linear programming problem with recourse, which we call the RP problem. A common way to approximate the RP problem, which is usually formulated in terms of scenarios, is to formulate the so-called Expected Value (EV) problem, which only considers the expectation of the random parameters of the RP problem. In this paper we introduce the Conditional Scenario (CS) problem which represents a midpoint between the RP and the EV problems regarding computational tractability and ability to deal with uncertainty. In the theoretical section we have analyzed some useful bounds related to the RP, EV and CS problems. In the numerical example here presented, the CS problem has outperformed both the EV problem in terms of solution quality, and the RP problem with the same number of scenarios as in the CS problem, in terms of solution time.

Suggested Citation

  • Beltran-Royo, C., 2017. "Two-stage stochastic mixed-integer linear programming: The conditional scenario approach," Omega, Elsevier, vol. 70(C), pages 31-42.
    • Handle: RePEc:eee:jomega:v:70:y:2017:i:c:p:31-42
    DOI: 10.1016/j.omega.2016.08.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316305758
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2016.08.010?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. Parisio, Alessandra & Neil Jones, Colin, 2015. "A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand," Omega, Elsevier, vol. 53(C), pages 97-103.
    2. Peter Kall & János Mayer, 2005. "Stochastic Linear Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-24440-2, September.
    3. Åsa Hallefjord & Sverre Storøy, 1990. "Aggregation and Disaggregation in Integer Programming Problems," Operations Research, INFORMS, vol. 38(4), pages 619-623, August.
    4. S. E. Wright, 1994. "Primal-Dual Aggregation and Disaggregation for Stochastic Linear Programs," Mathematics of Operations Research, INFORMS, vol. 19(4), pages 893-908, November.
    5. Georg Ch. Pflug & Alois Pichler, 2011. "Approximations for Probability Distributions and Stochastic Optimization Problems," International Series in Operations Research & Management Science, in: Marida Bertocchi & Giorgio Consigli & Michael A. H. Dempster (ed.), Stochastic Optimization Methods in Finance and Energy, edition 1, chapter 0, pages 343-387, Springer.
    6. Albareda-Sambola, Maria & Fernández, Elena & Saldanha-da-Gama, Francisco, 2011. "The facility location problem with Bernoulli demands," Omega, Elsevier, vol. 39(3), pages 335-345, June.
    7. Nickel, Stefan & Saldanha-da-Gama, Francisco & Ziegler, Hans-Peter, 2012. "A multi-stage stochastic supply network design problem with financial decisions and risk management," Omega, Elsevier, vol. 40(5), pages 511-524.
    8. Alonso-Ayuso, Antonio & Escudero, Laureano F. & Teresa Ortuno, M., 2003. "BFC, A branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs," European Journal of Operational Research, Elsevier, vol. 151(3), pages 503-519, December.
    9. David F. Rogers & Robert D. Plante & Richard T. Wong & James R. Evans, 1991. "Aggregation and Disaggregation Techniques and Methodology in Optimization," Operations Research, INFORMS, vol. 39(4), pages 553-582, August.
    10. Santoso, Tjendera & Ahmed, Shabbir & Goetschalckx, Marc & Shapiro, Alexander, 2005. "A stochastic programming approach for supply chain network design under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 96-115, November.
    11. Alonso-Ayuso, A. & Escudero, L. F. & Garín, A. & Ortuño, M. T. & Pérez, G., 2005. "On the product selection and plant dimensioning problem under uncertainty," Omega, Elsevier, vol. 33(4), pages 307-318, August.
    12. Paul H. Zipkin, 1980. "Bounds on the Effect of Aggregating Variables in Linear Programs," Operations Research, INFORMS, vol. 28(2), pages 403-418, April.
    13. Bertazzi, Luca & Bosco, Adamo & Laganà, Demetrio, 2015. "Managing stochastic demand in an Inventory Routing Problem with transportation procurement," Omega, Elsevier, vol. 56(C), pages 112-121.
    14. Paul H. Zipkin, 1980. "Bounds for Row-Aggregation in Linear Programming," Operations Research, INFORMS, vol. 28(4), pages 903-916, August.
    15. Samer Takriti & John R. Birge, 2000. "Lagrangian Solution Techniques and Bounds for Loosely Coupled Mixed-Integer Stochastic Programs," Operations Research, INFORMS, vol. 48(1), pages 91-98, February.
    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. Murwan Siddig & Yongjia Song, 2022. "Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse," Computational Optimization and Applications, Springer, vol. 81(1), pages 201-250, January.
    2. Alexander H. Gose & Brian T. Denton, 2016. "Sequential Bounding Methods for Two-Stage Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 351-369, May.
    3. John Turner, 2012. "The Planning of Guaranteed Targeted Display Advertising," Operations Research, INFORMS, vol. 60(1), pages 18-33, February.
    4. Merrick, James H. & Weyant, John P., 2019. "On choosing the resolution of normative models," European Journal of Operational Research, Elsevier, vol. 279(2), pages 511-523.
    5. Srinivasa, Anand V. & Wilhelm, Wilbert E., 1997. "A procedure for optimizing tactical response in oil spill clean up operations," European Journal of Operational Research, Elsevier, vol. 102(3), pages 554-574, November.
    6. Sodhi, ManMohan S. & Tang, Christopher S., 2009. "Modeling supply-chain planning under demand uncertainty using stochastic programming: A survey motivated by asset-liability management," International Journal of Production Economics, Elsevier, vol. 121(2), pages 728-738, October.
    7. Merrick, James H., 2016. "On representation of temporal variability in electricity capacity planning models," Energy Economics, Elsevier, vol. 59(C), pages 261-274.
    8. Escudero, Laureano F. & Landete, Mercedes & Rodríguez-Chía, Antonio M., 2011. "Stochastic set packing problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 232-240, June.
    9. ManMohan S. Sodhi, 2005. "LP Modeling for Asset-Liability Management: A Survey of Choices and Simplifications," Operations Research, INFORMS, vol. 53(2), pages 181-196, April.
    10. Klibi, Walid & Martel, Alain & Guitouni, Adel, 2016. "The impact of operations anticipations on the quality of stochastic location-allocation models," Omega, Elsevier, vol. 62(C), pages 19-33.
    11. Fu Lin & Sven Leyffer & Todd Munson, 2016. "A two-level approach to large mixed-integer programs with application to cogeneration in energy-efficient buildings," Computational Optimization and Applications, Springer, vol. 65(1), pages 1-46, September.
    12. Ali Fattahi & Sriram Dasu & Reza Ahmadi, 2023. "Peak-Load Energy Management by Direct Load Control Contracts," Management Science, INFORMS, vol. 69(5), pages 2788-2813, May.
    13. M S Sodhi & C S Tang, 2011. "Determining supply requirement in the sales-and-operations-planning (S&OP) process under demand uncertainty: a stochastic programming formulation and a spreadsheet implementation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(3), pages 526-536, March.
    14. Alonso-Ayuso, Antonio & Carvallo, Felipe & Escudero, Laureano F. & Guignard, Monique & Pi, Jiaxing & Puranmalka, Raghav & Weintraub, Andrés, 2014. "Medium range optimization of copper extraction planning under uncertainty in future copper prices," European Journal of Operational Research, Elsevier, vol. 233(3), pages 711-726.
    15. James H. Merrick & John E. T. Bistline & Geoffrey J. Blanford, 2021. "On representation of energy storage in electricity planning models," Papers 2105.03707, arXiv.org, revised May 2021.
    16. Roba W. Salem & Mohamed Haouari, 2017. "A simulation-optimisation approach for supply chain network design under supply and demand uncertainties," International Journal of Production Research, Taylor & Francis Journals, vol. 55(7), pages 1845-1861, April.
    17. Julia Higle & Suvrajeet Sen, 2006. "Multistage stochastic convex programs: Duality and its implications," Annals of Operations Research, Springer, vol. 142(1), pages 129-146, February.
    18. Vatsa, Amit Kumar & Jayaswal, Sachin, 2016. "A new formulation and Benders decomposition for the multi-period maximal covering facility location problem with server uncertainty," European Journal of Operational Research, Elsevier, vol. 251(2), pages 404-418.
    19. Laureano Escudero, 2009. "On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(1), pages 5-29, July.
    20. Xie, Fei & Huang, Yongxi, 2018. "A multistage stochastic programming model for a multi-period strategic expansion of biofuel supply chain under evolving uncertainties," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 130-148.

    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:jomega:v:70:y:2017:i:c:p:31-42. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.