IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v43y1995i3p477-490.html
   My bibliography  Save this article

A New Scenario Decomposition Method for Large-Scale Stochastic Optimization

Author

Listed:
  • John M. Mulvey

    (Princeton University, Princeton, New Jersey)

  • Andrzej Ruszczyński

    (International Institute for Applied Systems Analysis, Laxenburg, Austria)

Abstract

A novel parallel decomposition algorithm is developed for large, multistage stochastic optimization problems. The method decomposes the problem into subproblems that correspond to scenarios. The subproblems are modified by separable quadratic terms to coordinate the scenario solutions. Convergence of the coordination procedure is proven for linear programs. Subproblems are solved using a nonlinear interior point algorithm. The approach adjusts the degree of decomposition to fit the available hardware environment. Initial testing on a distributed network of workstations shows that an optimal number of computers depends upon the work per subproblem and its relation to the communication capacities. The algorithm has promise for solving stochastic programs that lie outside current capabilities.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:oropre:v:43:y:1995:i:3:p:477-490
    DOI: 10.1287/opre.43.3.477
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.43.3.477
    Download Restriction: no

    Citations

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


    Cited by:

    1. Helga Meier & Nicos Christofides & Gerry Salkin, 2001. "Capital Budgeting Under Uncertainty---An Integrated Approach Using Contingent Claims Analysis and Integer Programming," Operations Research, INFORMS, vol. 49(2), pages 196-206, April.
    2. Alizadeh, Morteza & Amiri-Aref, Mehdi & Mustafee, Navonil & Matilal, Sumohon, 2019. "A robust stochastic Casualty Collection Points location problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 965-983.
    3. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    4. T. Glenn Bailey & Paul A. Jensen & David P. Morton, 1999. "Response surface analysis of two‐stage stochastic linear programming with recourse," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(7), pages 753-776, October.
    5. 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.
    6. Shangyao Yan & Ching-Hui Tang, 2008. "An Integrated Framework for Intercity Bus Scheduling Under Stochastic Bus Travel Times," Transportation Science, INFORMS, vol. 42(3), pages 318-335, August.
    7. Hashem Omrani & Farzane Adabi & Narges Adabi, 2017. "Designing an efficient supply chain network with uncertain data: a robust optimization—data envelopment analysis approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 816-828, July.
    8. 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.
    9. Yan, Yongze & Hong, Liu & He, Xiaozheng & Ouyang, Min & Peeta, Srinivas & Chen, Xueguang, 2017. "Pre-disaster investment decisions for strengthening the Chinese railway system under earthquakes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 39-59.
    10. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    11. 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.
    12. X. W. Liu & M. Fukushima, 2006. "Parallelizable Preprocessing Method for Multistage Stochastic Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 131(3), pages 327-346, December.
    13. István Deák, 2011. "Testing successive regression approximations by large-scale two-stage problems," Annals of Operations Research, Springer, vol. 186(1), pages 83-99, June.
    14. Ricardo Collado & Dávid Papp & Andrzej Ruszczyński, 2012. "Scenario decomposition of risk-averse multistage stochastic programming problems," Annals of Operations Research, Springer, vol. 200(1), pages 147-170, November.
    15. 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.
    16. Chia-Hung Chen & Shangyao Yan & Miawjane Chen, 2010. "Short-term manpower planning for MRT carriage maintenance under mixed deterministic and stochastic demands," Annals of Operations Research, Springer, vol. 181(1), pages 67-88, December.
    17. Charles I. Nkeki, 2013. "Dynamic Optimization Technique for Distribution of Goods with Stochastic Shortages," Journal of Optimization, Hindawi, vol. 2013, pages 1-12, December.
    18. Kavinesh J. Singh & Andy B. Philpott & R. Kevin Wood, 2009. "Dantzig-Wolfe Decomposition for Solving Multistage Stochastic Capacity-Planning Problems," Operations Research, INFORMS, vol. 57(5), pages 1271-1286, October.
    19. Dimitris Bertsimas & Omid Nohadani & Kwong Meng Teo, 2010. "Robust Optimization for Unconstrained Simulation-Based Problems," Operations Research, INFORMS, vol. 58(1), pages 161-178, February.
    20. Tang, Yikuan & Zhang, Fan & Wang, Sufen & Zhang, Xiaodong & Guo, Shanshan & Guo, Ping, 2019. "A distributed interval nonlinear multiobjective programming approach for optimal irrigation water management in an arid area," Agricultural Water Management, Elsevier, vol. 220(C), pages 13-26.
    21. S C H Leung & K K Lai & W-L Ng & Y Wu, 2007. "A robust optimization model for production planning of perishable products," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 413-422, April.
    22. Fengqi You & Ignacio Grossmann, 2013. "Multicut Benders decomposition algorithm for process supply chain planning under uncertainty," Annals of Operations Research, Springer, vol. 210(1), pages 191-211, November.
    23. H. S. Yan, 2000. "Hierarchical Stochastic Production Planning with Delay Interaction," Journal of Optimization Theory and Applications, Springer, vol. 104(3), pages 659-689, March.
    24. 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.
    25. K. A. Ariyawansa & Andrew J. Felt, 2004. "On a New Collection of Stochastic Linear Programming Test Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 291-299, August.

    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:inm:oropre:v:43:y:1995:i:3:p:477-490. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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.

    We have no references for this item. You can help adding them by using 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.