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

Stopping Rules for a Class of Sampling-Based Stochastic Programming Algorithms

Author

Listed:
  • David P. Morton

    (The University of Texas at Austin, Austin, Texas)

Abstract

Monte Carlo sampling-based algorithms hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. In this paper, we develop a stopping rule theory for a class of algorithms that estimate bounds on the optimal objective function value by sampling. We provide rules for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence intervals for the quality of the proposed solution can be verified. Empirical coverage results are given for a simple example.

Suggested Citation

  • David P. Morton, 1998. "Stopping Rules for a Class of Sampling-Based Stochastic Programming Algorithms," Operations Research, INFORMS, vol. 46(5), pages 710-718, October.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:5:p:710-718
    DOI: 10.1287/opre.46.5.710
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.5.710
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.5.710?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
    ---><---

    References listed on IDEAS

    as
    1. M. I. Kusy & W. T. Ziemba, 1986. "A Bank Asset and Liability Management Model," Operations Research, INFORMS, vol. 34(3), pages 356-376, June.
    2. 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. Wim Ackooij & Welington Oliveira & Yongjia Song, 2019. "On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems," Computational Optimization and Applications, Springer, vol. 74(1), pages 1-42, September.
    2. Cerisola, Santiago & Latorre, Jesus M. & Ramos, Andres, 2012. "Stochastic dual dynamic programming applied to nonconvex hydrothermal models," European Journal of Operational Research, Elsevier, vol. 218(3), pages 687-697.
    3. Güzin Bayraksan & David P. Morton, 2011. "A Sequential Sampling Procedure for Stochastic Programming," Operations Research, INFORMS, vol. 59(4), pages 898-913, August.
    4. Jangho Park & Rebecca Stockbridge & Güzin Bayraksan, 2021. "Variance reduction for sequential sampling in stochastic programming," Annals of Operations Research, Springer, vol. 300(1), pages 171-204, May.
    5. Panos Parpas & Berk Ustun & Mort Webster & Quang Kha Tran, 2015. "Importance Sampling in Stochastic Programming: A Markov Chain Monte Carlo Approach," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 358-377, May.
    6. Vitor L. de Matos & David P. Morton & Erlon C. Finardi, 2017. "Assessing policy quality in a multistage stochastic program for long-term hydrothermal scheduling," Annals of Operations Research, Springer, vol. 253(2), pages 713-731, June.

    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. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    2. 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.
    3. Diana Barro & Elio Canestrelli, 2005. "Time and nodal decomposition with implicit non-anticipativity constraints in dynamic portfolio optimization," GE, Growth, Math methods 0510011, University Library of Munich, Germany.
    4. Klaassen, Pieter, 1997. "Solving stochastic programming models for asset/liability management using iterative disaggregation," Serie Research Memoranda 0010, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    5. Pieter Klaassen, 1998. "Financial Asset-Pricing Theory and Stochastic Programming Models for Asset/Liability Management: A Synthesis," Management Science, INFORMS, vol. 44(1), pages 31-48, January.
    6. Sandeep Rath & Kumar Rajaram, 2022. "Staff Planning for Hospitals with Implicit Cost Estimation and Stochastic Optimization," Production and Operations Management, Production and Operations Management Society, vol. 31(3), pages 1271-1289, March.
    7. Ioan Trenca & Daniela Bozga & Daniela Zapodeanu & Mihail Ioan Cociuba, 2017. "Considerations On The Strategy Of Commercial Banks In The Context Of The Financial System Development For The Period 2005-2013," Annals of Faculty of Economics, University of Oradea, Faculty of Economics, vol. 1(2), pages 248-258, December.
    8. Zapodeanu Daniela & Cociuba Mihai & Petria Nicolae, 2012. "The Role Of Value At Risk In The Management Of Asset And Liabilities," Annals of Faculty of Economics, University of Oradea, Faculty of Economics, vol. 1(2), pages 635-640, December.
    9. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    10. 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.
    11. 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.
    12. Robert Ferstl & Alexander Weissensteiner, 2011. "Backtesting Short-Term Treasury Management Strategies Based on Multi-Stage Stochastic Programming," Palgrave Macmillan Books, in: Gautam Mitra & Katharina Schwaiger (ed.), Asset and Liability Management Handbook, chapter 19, pages 469-494, Palgrave Macmillan.
    13. Klaassen, Pieter, 1997. "Discretized reality and spurious profits in stochastic programming models for asset/liability management," Serie Research Memoranda 0011, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    14. Kai Huang & Shabbir Ahmed, 2009. "The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty," Operations Research, INFORMS, vol. 57(4), pages 893-904, August.
    15. Peter Kall & János Mayer, 2006. "Some insights into the solution algorithms for SLP problems," Annals of Operations Research, Springer, vol. 142(1), pages 147-164, February.
    16. Diana Barro & Elio Canestrelli, 2011. "Combining stochastic programming and optimal control to solve multistage stochastic optimization problems," Working Papers 2011_24, Department of Economics, University of Venice "Ca' Foscari", revised 2011.
    17. 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.
    18. Li, Y.P. & Huang, G.H. & Zhang, N. & Nie, S.L., 2011. "An inexact-stochastic with recourse model for developing regional economic-ecological sustainability under uncertainty," Ecological Modelling, Elsevier, vol. 222(2), pages 370-379.
    19. 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.
    20. Nick Georgiopoulos, 2020. "Liability-driven investments of life insurers under investment credit risk," Risk Management, Palgrave Macmillan, vol. 22(2), pages 83-107, June.

    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:46:y:1998:i:5:p:710-718. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.