Department of Industrial and Operations Engineering
University of Michigan
Recent Presentations or Work
John R. Birge, Christopher J. Donohue, Derek F. Holmes, Oleg G. Svintsitski
Supported in part by the National Science Foundation under Grant DDM-9215921.
Most sequential decisions must be made in uncertain environments.
Multistage stochastic programs may model these decisions by seeking
to find decision variable levels that attain an optimal expected value
subject to possibly uncertain constraints on available resources.
Multistage stochastic programs have been applied to a variety
of problems, ranging from forestry management to portfolio optimization
and capacity expansion.
Solving a
multistage stochastic program can be viewed as solving a large
tree of linear programs. A common approach for solving these problems
is the nested decomposition algorithm, which moves up and down the tree
solving nodes and passing information between nodes. The natural
independence of subtrees suggests that much of the computational
effort of the nested decomposition algorithm can run in parallel
across numbers of fast processors. This research explores the
advantages of such parallel implementations over serial
implementations and compares alternative sequencing protocols
for parallel processors. Computational experience on a large test
set of practical problems with up to 1.5 million constraints and
almost 5 million variables suggests that parallel implementations
may indeed work well.
While a variety of ways may be found to split a problem tree
for parallelized calculations, a reasonable principle here is
to assign as large a subtree as possible to each slave, thereby
decreasing the size of the tree left for the master task.
The obvious result then is spreading equal portions of the original
problem tree among processors available for calculations (assuming
the processors have similar speeds and abilities).
Implemented parallel software allows an arbitrary number of processors
to be used. Generally, the problem tree can be split in any place.
While the parallel code implements an algorithm identical to the
one in the serial code, a parallelized solution path does not
necessarily repeat the path that would be obtained from the
serial implementation.
The algorithm implementation was tested
on a suite of large stochastic programs from the literature.
Serial and parallel solution times for two selected
problems are plotted on the figure. Comparisons between our
algorithm (ND-UM) and selected other existing techniques are also
provided. The results indicate that parallelization generally works well,
but success is relatively problem and sequencing protocol dependent.
In some cases, the parallel algorithm takes a much faster solution
path than the serial code, and can give near-linear or even
superlinear performance.
Derek Holmes
Solving many linear programs that difer only in their RHSs is a common problem
in stochastic programming. On SIMD machines, these problems may be solved
by pivoting to a new basis in each processor. The time to solve all problems
will then be the time to solve the problem that requires the most pivots. We
discuss two methods for balancing the work more evenly: ``Planting'' different
initial bases across processors and ``trading'' problem to try to force each processor
to move to a basis not already considered. Computational results obtained on an
IBM SP-1 are provided.