Optimization Online


Scenario Decomposition for 0-1 Stochastic Programs: Improvements and Asynchronous Implementation

Kevin Ryan(kryan31***at***gatech.edu)
Deepak Rajan(rajan3***at***llnl.gov)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)

Abstract: A recently proposed scenario decomposition algorithm for stochastic 0-1 programs finds an optimal solution by evaluating and removing individual solutions that are discovered by solving scenario subproblems. In this work, we develop an asynchronous, distributed implementation of the algorithm which has computational advantages over existing synchronous implementations of the algorithm. Improvements to both the synchronous and asynchronous algorithm are proposed. We test the results on well known stochastic 0-1 programs from the SIPLIB test library and are able to solve previously unsolved instances from the test set.

Keywords: two-stage stochastic mixed-integer programming, scenario decomposition, distributed memory algorithm

Category 1: Stochastic Programming

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


Download: [PDF]

Entry Submitted: 11/13/2015
Entry Accepted: 11/13/2015
Entry Last Modified: 11/13/2015

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