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 language | English |
---|---|
Pages (from-to) | 1772-1800 |
Number of pages | 29 |
Journal | SIAM Journal on Optimization |
Volume | 27 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2017 |
Externally published | Yes |
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]).
Funders | Funder number |
---|---|
National Science Foundation | 1435771, CMMI-1436177, CMMI-1435771 |
Booth School of Business, University of Chicago |
Keywords
- Bounding
- Mixed-integer
- Multistage
- Parallel computing
- Stochastic programming