Computations in Multiperiod Stochastic Programming

TB21.1 Issues in Parallel Implementation of a Multi-Cut Method Alan J. King --- IBM, TJ Watson Res. Ctr., Yorktown Heights, NY 10598 ,

We discuss a message passing implementation of a multicut parallel¨ Benders algorithm. Particular issues include partitioning scenario¨ tree into subproblems and assigning subproblems to processors.¨ Solution times are often quite sensitive to the tree partition¨ configuration, which in turn leads to a requirement that multiple¨ subproblems might be assigned per processor.

TB21.2 An Implementation of the Nested Decomposition Method for Multistage Stochastic Linear Programs John R. Birge, Christopher Donohue, Derek Holmes --- Univ. of MI, Dept. of IOE, 1205 Beal Ave., Ann Arbor, MI 48109-2117, (jrbirge@umich.edu)

Solving a multistage stochastic LP can be viewed as solving a large¨ tree of LPs, with each node in the tree representing a particular¨ subproblem in a specific stage. The nested decomposition method has¨ proven to be an effective method for solving these problems. An¨ implementation of the ND-UM was developed at the University of¨ Michigan to explore benefits from parallel processing...

TB21.3 A Stochastic Scenario Decomposition Algorithm for Multi-Stage Stochastic Linear Programming Julia L. Higle, Suvrajeet Sen --- Univ. of AZ, Dept. of SIE, Tucson, AZ 85721 , (julie@sie.arizona.edu)

We present a new sampling-based procedure for multi-stage stochastic¨ LPs. The method is based on an extension of a statistical optimality¨ test that has been proposed by the authors. The SSD algorithm can be¨ conceptualized and implemented without regard to the number of¨ stages in the stochastic LP.

TB21.4 Solving Multistage Stochastic Programs via Nonanticipativity Aggregation Chanaka Edirisinghe --- Univ. of TN, MS Program, 610 Stokely Mgmt. Ctr., Knoxville, TN 37996 , (chanaka@utk.edu)

A sequential approximation procedure for solving multistage¨ stochastic programs is presented. The computational advantage of the¨ method is due to an iterative aggregation of the nonanticipativity¨ conditions. Applicaiton of the method to asset allocation problems¨ where technology matrices are stochastic will be discussed along¨ with computational results.