A scalable bounding method for multi-stage stochastic integer programs

Many dynamic decision problems involving uncertainty can be appropriately modeled as multi-stage 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 Sandikci et al. (2013) on two-stage stochastic mixed-integer-programs (SMIPs), this paper develops a bounding method for general multi-stage SMIPs that is 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, which can address truly large-scale instances. Extensive computational experiments with large-scale instances (with up to 40 million scenarios, 520 million binary variables, and 330 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.

Citation

Chicago Booth Working Paper No. 14-21, May 2014

Article

Download

View A scalable bounding method for multi-stage stochastic integer programs