Optimization Online


An Adaptive Partition-based Approach for Solving Two-stage Stochastic Programs with Fixed Recourse

Yongjia Song(ysong3***at***vcu.edu)
James Luedtke(jrluedt1***at***wisc.edu)

Abstract: We study an adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse. A partition-based formulation is a relaxation of the original stochastic program, and we study a finitely converging algorithm in which the partition is adaptively adjusted until it yields an optimal solution. A solution guided refinement strategy is developed to refine the partition by exploiting the relaxation solution obtained from a partition. In addition to refinement, we show that in the case of stochastic linear programs, it is possible to merge some components in a partition, without weakening the corresponding relaxation bound, thus allowing the partition size to be kept small. We also show that for stochastic linear programs with simple recourse, there exists a small partition that yields an optimal solution. The size of this partition is independent of the number of scenarios used in the model. Our computational results show that the proposed adaptive partition-based approach converges very fast to a small partition for our test instances. In particular, on our test instances the proposed approach outperforms basic versions of Benders decomposition and is competitive with the state-of-art methods such as the level method for stochastic linear programs with fixed recourse.

Keywords: Two-stage stochastic programming, scenario partitions, simple recourse

Category 1: Stochastic Programming


Download: [PDF]

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