Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs
Gabriel L. Zenarosa(glz5pitt.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.
Entry Submitted: 09/16/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|