IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v64y2016i2d10.1007_s10589-015-9813-x.html
   My bibliography  Save this article

Clustering-based preconditioning for stochastic programs

Author

Listed:
  • Yankai Cao

    (Purdue University)

  • Carl D. Laird

    (Purdue University)

  • Victor M. Zavala

    (University of Wisconsin-Madison)

Abstract

We present a clustering-based preconditioning strategy for KKT systems arising in stochastic programming within an interior-point framework. The key idea is to perform adaptive clustering of scenarios (inside-the-solver) based on their influence on the problem at hand. This approach thus contrasts with existing (outside-the-solver) approaches that cluster scenarios based on problem data alone. We derive spectral and error properties for the preconditioner and demonstrate that scenario compression rates of up to 94 % can be obtained, leading to dramatic computational savings. In addition, we demonstrate that the proposed preconditioner can avoid scalability issues of Schur decomposition in problems with large first-stage dimensionality.

Suggested Citation

  • Yankai Cao & Carl D. Laird & Victor M. Zavala, 2016. "Clustering-based preconditioning for stochastic programs," Computational Optimization and Applications, Springer, vol. 64(2), pages 379-406, June.
    • Handle: RePEc:spr:coopap:v:64:y:2016:i:2:d:10.1007_s10589-015-9813-x
    DOI: 10.1007/s10589-015-9813-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-015-9813-x
    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/s10589-015-9813-x?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. 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.
    2. Latorre, Jesus M & Cerisola, Santiago & Ramos, Andres, 2007. "Clustering algorithms for scenario tree generation: Application to natural hydro inflows," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1339-1353, September.
    3. Geoffrey Pritchard & Golbon Zakeri & Andrew Philpott, 2010. "A Single-Settlement, Energy-Only Electric Power Market for Unpredictable and Intermittent Participants," Operations Research, INFORMS, vol. 58(4-part-2), pages 1210-1219, August.
    4. Victor M. Zavala & Kibaek Kim & Mihai Anitescu & John Birge, 2017. "A Stochastic Electricity Market Clearing Formulation with Consistent Pricing Properties," Operations Research, INFORMS, vol. 65(3), pages 557-576, June.
    5. Paul H. Zipkin, 1980. "Bounds for Row-Aggregation in Linear Programming," Operations Research, INFORMS, vol. 28(4), pages 903-916, August.
    6. Cosmin Petra & Mihai Anitescu, 2012. "A preconditioning technique for Schur complement systems arising in stochastic optimization," Computational Optimization and Applications, Springer, vol. 52(2), pages 315-344, June.
    7. Michael S. Casey & Suvrajeet Sen, 2005. "The Scenario Generation Algorithm for Multistage Stochastic Linear Programming," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 615-631, August.
    8. Holger Heitsch & Werner Römisch, 2009. "Scenario tree reduction for multistage stochastic programs," Computational Management Science, Springer, vol. 6(2), pages 117-133, May.
    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. Castro, Jordi & Nasini, Stefano, 2021. "A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks," European Journal of Operational Research, Elsevier, vol. 290(3), pages 857-869.
    2. Sungho Shin & Ophelia S Venturelli & Victor M Zavala, 2019. "Scalable nonlinear programming framework for parameter estimation in dynamic biological system models," PLOS Computational Biology, Public Library of Science, vol. 15(3), pages 1-29, March.

    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. Fei, Xin & Gülpınar, Nalân & Branke, Jürgen, 2019. "Efficient solution selection for two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 277(3), pages 918-929.
    2. Wim van Ackooij & Welington de Oliveira & Yongjia Song, 2018. "Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 57-70, February.
    3. Ordoudis, Christos & Delikaraoglou, Stefanos & Kazempour, Jalal & Pinson, Pierre, 2020. "Market-based coordination of integrated electricity and natural gas systems under uncertain supply," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1105-1119.
    4. Xin Shi & Alberto J. Lamadrid L. & Luis F. Zuluaga, 2021. "Revenue Adequate Prices for Chance-Constrained Electricity Markets with Variable Renewable Energy Sources," Papers 2105.01233, arXiv.org.
    5. Ratha, Anubhav & Pinson, Pierre & Le Cadre, Hélène & Virag, Ana & Kazempour, Jalal, 2023. "Moving from linear to conic markets for electricity," European Journal of Operational Research, Elsevier, vol. 309(2), pages 762-783.
    6. 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.
    7. Bjørndal, Endre & Bjørndal, Mette & Midthun, Kjetil & Tomasgard, Asgeir, 2018. "Stochastic electricity dispatch: A challenge for market design," Energy, Elsevier, vol. 150(C), pages 992-1005.
    8. Zhang, Weiqi & Zavala, Victor M., 2022. "Remunerating space–time, load-shifting flexibility from data centers in electricity markets," Applied Energy, Elsevier, vol. 326(C).
    9. Michal Kaut & Stein Wallace, 2011. "Shape-based scenario generation using copulas," Computational Management Science, Springer, vol. 8(1), pages 181-199, April.
    10. Bjørndal, Endre & Bjørndal, Mette & Midthun, Kjetil & Tomasgard, Asgeir, 2016. "Stochastic Electricity Dispatch: A challenge for market design," Discussion Papers 2016/11, Norwegian School of Economics, Department of Business and Management Science.
    11. Hohl, Cody & Lo Prete, Chiara & Radhakrishnan, Ashish & Webster, Mort, 2023. "Intraday markets, wind integration and uplift payments in a regional U.S. power system," Energy Policy, Elsevier, vol. 175(C).
    12. Morales, J.M. & Muñoz, M.A. & Pineda, S., 2023. "Prescribing net demand for two-stage electricity generation scheduling," Operations Research Perspectives, Elsevier, vol. 10(C).
    13. Philip A. Tominac & Victor M. Zavala, 2020. "Economic Properties of Multi-Product Supply Chains," Papers 2006.03467, arXiv.org, revised Jul 2020.
    14. Bjørndal, Endre & Bjørndal, Mette & Midthun, Kjetil & Zakeri, Golbon, 2016. "Congestion Management in a Stochastic Dispatch Model for Electricity Markets," Discussion Papers 2016/12, Norwegian School of Economics, Department of Business and Management Science.
    15. Michael Freimer & Jeffrey Linderoth & Douglas Thomas, 2012. "The impact of sampling methods on bias and variance in stochastic linear programs," Computational Optimization and Applications, Springer, vol. 51(1), pages 51-75, January.
    16. Zéphyr, Luckny & Lang, Pascal & Lamond, Bernard F. & Côté, Pascal, 2017. "Approximate stochastic dynamic programming for hydroelectric production planning," European Journal of Operational Research, Elsevier, vol. 262(2), pages 586-601.
    17. Alexandre Forel & Martin Grunow, 2023. "Dynamic stochastic lot sizing with forecast evolution in rolling‐horizon planning," Production and Operations Management, Production and Operations Management Society, vol. 32(2), pages 449-468, February.
    18. 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.
    19. Chen, Lijian, 2020. "Determine the cost of denying boarding to passengers: An optimization-based approach," International Journal of Production Economics, Elsevier, vol. 220(C).
    20. D. Kuhn, 2009. "Convergent Bounds for Stochastic Programs with Expected Value Constraints," Journal of Optimization Theory and Applications, Springer, vol. 141(3), pages 597-618, 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:spr:coopap:v:64:y:2016:i:2:d:10.1007_s10589-015-9813-x. 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.