IDEAS home Printed from https://ideas.repec.org/p/wop/iasawp/wp96065.html
   My bibliography  Save this paper

A Branch and Bound Method for Stochastic Global Optimization

Author

Listed:
  • V.I. Norkin
  • G.C. Pflug
  • A. Ruszczynski

Abstract

A stochastic version of the branch and bound method is proposed for solving stochastic global optimization problems. The method, instead of deterministic bounds, uses stochastic upper and lower estimates of the optimal value of subproblems, to guide the partitioning process. Almost sure convergence of the method is proved and random accuracy estimates derived. Methods for constructing random bounds for stochastic global optimization problems are discussed. The theoretical considerations are illustrated with an example of a facility location problem.

Suggested Citation

  • 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.
    • Handle: RePEc:wop:iasawp:wp96065
    as

    Download full text from publisher

    File URL: http://www.iiasa.ac.at/Publications/Documents/WP-96-065.pdf
    Download Restriction: no
    File URL: http://www.iiasa.ac.at/Publications/Documents/WP-96-065.ps
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. labbe, M. & Peeters, D. & Thisse, J.F., 1992. "Location on Networks," Papers 9216, Universite Libre de Bruxelles - C.E.M.E..
    3. Vladimir I. Norkin & Yuri M. Ermoliev & Andrzej Ruszczyński, 1998. "On Optimal Allocation of Indivisibles Under Uncertainty," Operations Research, INFORMS, vol. 46(3), pages 381-395, June.
    4. 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.
    5. 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. Y.M. Ermoliev & V.I. Norkin, 1998. "Monte Carlo Optimization and Path Dependent Nonstationary Laws of Large Numbers," Working Papers ir98009, International Institute for Applied Systems Analysis.
    2. Didier Rullière & Alaeddine Faleh & Frédéric Planchet & Wassim Youssef, 2013. "Exploring or reducing noise? A global optimization algorithm in the presence of noise," Post-Print hal-00759677, HAL.
    3. repec:hal:wpaper:hal-00759677 is not listed on IDEAS
    4. Johannes Royset, 2013. "On sample size control in sample average approximations for solving smooth stochastic programs," Computational Optimization and Applications, Springer, vol. 55(2), pages 265-309, June.
    5. Contreras, Ivan & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Stochastic uncapacitated hub location," European Journal of Operational Research, Elsevier, vol. 212(3), pages 518-528, August.
    6. Lee, Der-Horng & Dong, Meng & Bian, Wen, 2010. "The design of sustainable logistics network under uncertainty," International Journal of Production Economics, Elsevier, vol. 128(1), pages 159-166, November.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. A. Ruszczynski, 1994. "On Augmented Lagrangian Decomposition Methods For Multistage Stochastic Programs," Working Papers wp94005, International Institute for Applied Systems Analysis.
    9. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    10. Martin Šmíd & Václav Kozmík, 2024. "Approximation of multistage stochastic programming problems by smoothed quantization," Review of Managerial Science, Springer, vol. 18(7), pages 2079-2114, July.
    11. Eun, Joonyup & Kim, Sang-Phil & Yih, Yuehwern & Tiwari, Vikram, 2019. "Scheduling elective surgery patients considering time-dependent health urgency: Modeling and solution approaches," Omega, Elsevier, vol. 86(C), pages 137-153.
    12. 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.
    13. Lijian Chen & Tito Homem-de-Mello, 2010. "Re-solving stochastic programming models for airline revenue management," Annals of Operations Research, Springer, vol. 177(1), pages 91-114, June.
    14. Ankur Kulkarni & Uday Shanbhag, 2012. "Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms," Computational Optimization and Applications, Springer, vol. 51(1), pages 77-123, January.
    15. 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.
    16. Panos Parpas & Berç Rustem, 2007. "Computational Assessment of Nested Benders and Augmented Lagrangian Decomposition for Mean-Variance Multistage Stochastic Problems," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 239-247, May.
    17. Manuel Laguna, 1998. "Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty," Management Science, INFORMS, vol. 44(11-Part-2), pages 101-110, November.
    18. 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.
    19. Shabbir Ahmed & Nikolaos V. Sahinidis, 2003. "An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion," Operations Research, INFORMS, vol. 51(3), pages 461-471, June.
    20. Jie Sun & Xinwei Liu, 2006. "Scenario Formulation of Stochastic Linear Programs and the Homogeneous Self-Dual Interior-Point Method," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 444-454, November.

    More about this item

    Statistics

    Access and download statistics

    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:wop:iasawp:wp96065. 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: Thomas Krichel (email available below). General contact details of provider: https://edirc.repec.org/data/iiasaat.html .

    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.