IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v15y2018i3d10.1007_s10287-018-0311-3.html
   My bibliography  Save this article

A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs

Author

Listed:
  • Semih Atakan

    (University of Southern California)

  • Suvrajeet Sen

    (University of Southern California)

Abstract

Progressive Hedging (PH) is a well-known algorithm for solving multi-stage stochastic convex optimization problems. Most previous extensions of PH for mixed-integer stochastic programs have been implemented without convergence guarantees. In this paper, we present a new framework that shows how PH can be utilized while guaranteeing convergence to globally optimal solutions of mixed-integer stochastic convex programs. We demonstrate the effectiveness of the proposed framework through computational experiments.

Suggested Citation

  • Semih Atakan & Suvrajeet Sen, 2018. "A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs," Computational Management Science, Springer, vol. 15(3), pages 501-540, October.
    • Handle: RePEc:spr:comgts:v:15:y:2018:i:3:d:10.1007_s10287-018-0311-3
    DOI: 10.1007/s10287-018-0311-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-018-0311-3
    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-018-0311-3?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. Pagès-Bernaus, Adela & Pérez-Valdés, Gerardo & Tomasgard, Asgeir, 2015. "A parallelised distributed implementation of a Branch and Fix Coordination algorithm," European Journal of Operational Research, Elsevier, vol. 244(1), pages 77-85.
    2. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    3. LOUVEAUX, François V., 1980. "A solution method for multistage stochastic programs with recourse with application to an energy investment problem," LIDAM Reprints CORE 415, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. 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.
    5. 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.
    6. John M. Mulvey & Andrzej Ruszczyński, 1995. "A New Scenario Decomposition Method for Large-Scale Stochastic Optimization," Operations Research, INFORMS, vol. 43(3), pages 477-490, June.
    7. Francois V. Louveaux, 1980. "A Solution Method for Multistage Stochastic Programs with Recourse with Application to an Energy Investment Problem," Operations Research, INFORMS, vol. 28(4), pages 889-902, August.
    8. Laureano Escudero & Araceli Garín & María Merino & Gloria Pérez, 2009. "BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0–1 problems," 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 96-122, July.
    9. Robert E. Bixby, 2002. "Solving Real-World Linear Programs: A Decade and More of Progress," Operations Research, INFORMS, vol. 50(1), pages 3-15, February.
    10. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    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. Can Li & Ignacio E. Grossmann, 2019. "A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables," Journal of Global Optimization, Springer, vol. 75(2), pages 247-272, October.
    2. Nur Banu Demir & Serhat Gul & Melih Çelik, 2021. "A stochastic programming approach for chemotherapy appointment scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(1), pages 112-133, February.
    3. Georgia Fargetta & Antonino Maugeri & Laura Scrimali, 2022. "A Stochastic Nash Equilibrium Problem for Medical Supply Competition," Journal of Optimization Theory and Applications, Springer, vol. 193(1), pages 354-380, June.
    4. Can Li & Ignacio E. Grossmann, 2019. "A finite $$\epsilon $$ϵ-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables," Journal of Global Optimization, Springer, vol. 75(4), pages 921-947, December.
    5. Escudero, Laureano F. & Garín, M. Araceli & Monge, Juan F. & Unzueta, Aitziber, 2020. "Some matheuristic algorithms for multistage stochastic optimization models with endogenous uncertainty and risk management," European Journal of Operational Research, Elsevier, vol. 285(3), pages 988-1001.
    6. Atakan, Semih & Gangammanavar, Harsha & Sen, Suvrajeet, 2022. "Towards a sustainable power grid: Stochastic hierarchical planning for high renewable integration," European Journal of Operational Research, Elsevier, vol. 302(1), pages 381-391.

    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. 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.
    2. 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.
    3. 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).
    4. Aldasoro, Unai & Escudero, Laureano F. & Merino, María & Pérez, Gloria, 2017. "A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large sized multistage stochastic mixed 0–1 problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 590-606.
    5. Unai Aldasoro & María Merino & Gloria Pérez, 2019. "Time consistent expected mean-variance in multistage stochastic quadratic optimization: a model and a matheuristic," Annals of Operations Research, Springer, vol. 280(1), pages 151-187, September.
    6. V.I. Norkin & G.C. Pflug & A. Ruszczynski, 1996. "A Branch and Bound Method for Stochastic Global Optimization," Working Papers wp96065, International Institute for Applied Systems Analysis.
    7. Maqsood, Imran & Huang, Guo H. & Scott Yeomans, Julian, 2005. "An interval-parameter fuzzy two-stage stochastic program for water resources management under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 208-225, November.
    8. 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.
    9. Torres-Rincón, Samuel & Sánchez-Silva, Mauricio & Bastidas-Arteaga, Emilio, 2021. "A multistage stochastic program for the design and management of flexible infrastructure networks," Reliability Engineering and System Safety, Elsevier, vol. 210(C).
    10. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2019. "Robust Dual Dynamic Programming," Operations Research, INFORMS, vol. 67(3), pages 813-830, May.
    11. Fernando Veliz & Jean-Paul Watson & Andres Weintraub & Roger Wets & David Woodruff, 2015. "Stochastic optimization models in forest planning: a progressive hedging solution approach," Annals of Operations Research, Springer, vol. 232(1), pages 259-274, September.
    12. Pablo Salas, 2013. "Literature Review of Energy-Economics Models, Regarding Technological Change and Uncertainty," 4CMR Working Paper Series 003, University of Cambridge, Department of Land Economy, Cambridge Centre for Climate Change Mitigation Research.
    13. Castro, Jordi & Escudero, Laureano F. & Monge, Juan F., 2023. "On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach," European Journal of Operational Research, Elsevier, vol. 310(1), pages 268-285.
    14. Cooper, W. W. & Hemphill, H. & Huang, Z. & Li, S. & Lelas, V. & Sullivan, D. W., 1997. "Survey of mathematical programming models in air pollution management," European Journal of Operational Research, Elsevier, vol. 96(1), pages 1-35, January.
    15. Gyana R. Parija & Shabbir Ahmed & Alan J. King, 2004. "On Bridging the Gap Between Stochastic Integer Programming and MIP Solver Technologies," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 73-83, February.
    16. Ningyuan Chen & Steven Kou & Chun Wang, 2018. "A Partitioning Algorithm for Markov Decision Processes with Applications to Market Microstructure," Management Science, INFORMS, vol. 64(2), pages 784-803, February.
    17. Jesús Latorre & Santiago Cerisola & Andrés Ramos & Rafael Palacios, 2009. "Analysis of stochastic problem decomposition algorithms in computational grids," Annals of Operations Research, Springer, vol. 166(1), pages 355-373, February.
    18. Bülbül, Kerem & Noyan, Nilay & Erol, Hazal, 2021. "Multi-stage stochastic programming models for provisioning cloud computing resources," European Journal of Operational Research, Elsevier, vol. 288(3), pages 886-901.
    19. Marco Colombo & Andreas Grothey, 2013. "A decomposition-based crash-start for stochastic programming," Computational Optimization and Applications, Springer, vol. 55(2), pages 311-340, June.
    20. A. Ruszczynski, 1994. "On Augmented Lagrangian Decomposition Methods For Multistage Stochastic Programs," Working Papers wp94005, International Institute for Applied Systems Analysis.

    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:15:y:2018:i:3:d:10.1007_s10287-018-0311-3. 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.