A scalable bounding method for multistage stochastic programs

Burhaneddin Sandikči, Osman Y. Özaltin

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

Many dynamic decision problems involving uncertainty can be appropriately modeled as multistage stochastic programs. However, most practical instances are so large and/or complex that it is impossible to solve them on a single computer, especially due to memory limitations. Extending the work of [B. Sandikci, N. Kong, and A. J. Schaefer, Math. Program., 138(2013), pp. 253-272] on two-stage stochastic mixed-integer programs, this paper considers general multistage stochastic programs and develops a bounding method based on scenario decomposition. This method is broadly applicable, as it does not assume any problem structure including convexity. Moreover, it naturally fits into a distributed computing environment. Computational experiments with large-scale instances (with up to 100 million scenarios, about 1.5 billion decision variables-85% binary- and 800 million constraints) demonstrate that the proposed method scales nicely with problem size and has immense potential to obtain high-quality solutions to practical instances within a reasonable time frame.

Original languageEnglish
Pages (from-to)1772-1800
Number of pages29
JournalSIAM Journal on Optimization
Volume27
Issue number3
DOIs
Publication statusPublished - 2017
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2017 SIAM Unauthorized reproduction of this article is prohibited.

Funding

∗Received by the editors May 17, 2016; accepted for publication (in revised form) March 9, 2017; published electronically August 17, 2017. An earlier version of this paper is available from http://ssrn.com/abstract=2466650. http://www.siam.org/journals/siopt/27-3/M107559.html Funding: This work was supported in part by National Science Foundation grants CMMI-1435771 and CMMI-1436177. The first author received financial support from the University of Chicago Booth School of Business. The second author received support from the Laboratory for Analytic Sciences. †Booth School of Business, University of Chicago, Chicago, IL 60657 ([email protected]). ‡Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27695 ([email protected]).

FundersFunder number
National Science Foundation1435771, CMMI-1436177, CMMI-1435771
Booth School of Business, University of Chicago

    Keywords

    • Bounding
    • Mixed-integer
    • Multistage
    • Parallel computing
    • Stochastic programming

    Fingerprint

    Dive into the research topics of 'A scalable bounding method for multistage stochastic programs'. Together they form a unique fingerprint.

    Cite this