Optimization Online


A scalable bounding method for multi-stage stochastic integer programs

Burhaneddin Sandikci(burhan***at***chicagobooth.edu)
Osman Y. Ozaltin(oyozalti***at***ncsu.edu)

Abstract: 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.

Keywords: Stochastic programming, Multi-stage, Mixed-integer variables, Bounding, Parallel computing

Category 1: Stochastic Programming

Category 2: Integer Programming

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

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

Download: [PDF]

Entry Submitted: 07/16/2014
Entry Accepted: 07/16/2014
Entry Last Modified: 07/16/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society