Optimization Online


Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

Gabriel L. Zenarosa(glz5***at***pitt.edu)
Oleg A. Prokopyev(prokopyev***at***engr.pitt.edu)
Andrew J. Schaefer(schaefer***at***ie.pitt.edu)

Abstract: Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller trees using vertex cuts, and combines the solutions of the resulting subproblems to generate the bounds. Lower bounds are calculated as the weighted sum of the solutions to the subproblems, and upper bounds are calculated using best root-to-cut decisions among all subproblems. We developed a multithreaded implementation of our method to solve the "embarrassingly parallel" subproblems. We evaluate our method on a number of test instances from the existing literature, and we found that our bounds are competitive with those of a state-of-the art commercial solver.

Keywords: stochastic programming, mixed-integer programming, bounds

Category 1: Stochastic Programming

Category 2: Integer Programming

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

Citation: Working Paper, Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, Pittsburgh, PA 15261, USA, September 2014.

Download: [PDF]

Entry Submitted: 09/16/2014
Entry Accepted: 09/16/2014
Entry Last Modified: 09/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