This page serves as a repository for recent computational results for large scale
stochastic programming problems. The success of this page and this efforts depends
on contributions. To do so, please send email to
jrbirge@engin.umich.edu
or click here.
Abstract:
While decisions frequently have uncertain consequences, optimal decision models often replace these
uncertainties with averages or best estimates. Limited computational capability may have motivated this
practive in the past. Recent computational advances have, however, greatly expanded the range of
stochastic programs, optimal decision models with explicit consideration of uncertainties.
This paper describes basic methodology in stochastic programming, recent developments in computation,
and some practical application examples.
Recent results in Computational Stochastic Programming
This list reports recent results on stochastic programming problems
available online. Each report contains all the information that was given by researchers
to the maintainer of this page.
Predictor-Corrector Interior Point Codes
Courtesy of Joe Czyzyk, Argonne National Labs
Algorithm descriptions
In the following, PCx is a public domain Predictor-Corector code under
development at by Joe Czyzyk at Argonne National Labs. The
code fo1aug is a predictor corrector code with an augmented lagrangian solver.
For details see Prof. S. Mehrotra's Homepage .
To get further descriptions, click here!
Test conditions
Tolerances:
primal and dual relative infeasibility : 1.0e-7
objective tolerance 1.0e-8
Hardware:
Problems were converted to det. equiv. form using Joe's deteq converter
(to appear along side POSTS soon!) and solved on one node of the IBM SP-1
at Argonne. Each node has 128 MB memory, and is equivalent to an RS/6000/370.
Results
Det. Equiv. PCx fo1aug
Problem Opt. Obj. Value Obj. value time obj. time
-----------------------------------------------------------------
PLTEXP
pltexpA2.6 -9.479 -9.4793536 2.82 -9.4793536 1.14
pltexpA2.16 -9.663 -9.6633082 47.81 -9.663308245 3.19
pltexpA3.6 -13.969 -13.9693692 76.70 -13.96936919 18.98
pltexpA3.16 -14.267 (36 it 3dgts) 40min no space
pltexpA4.6 -19.599 -19.599411 1113.77 -19.5994114 137.30
pltexpA4.16 -18.849
pltexpA5.6 -23.214
pltexpA6.6
pltexpB3.6 -13.6432 -13.6432265 20.52 -13.643226 8.91
pltexpB4.6 -17.9282 -17.928192 156.02 -17.92819208 16.33
pltexpB5.6 -23.870 -23.8433844 632.58 -23.8433844 54.41
-----------------------------------------------------------------
SCFXM
fxm2.6 18416.686 1.8 e+04 4.92 18417.06557 7.88
fxm2.16 18416.655 1.84e+04 22.95 18416.75902 24.83
fxm3.6 18615.932 1.86e+04 24.03 18616.0420 37.75
fxm3.16 18438.891 error error
fxm4.6 18616.224 bad solution 90.59 error
fxm4.16 18438.891
-----------------------------------------------------------------
STORM
storm2.8 15535231.897 15535236.6 136.32 15535236.6301 55.19
storm2.27 15508982.306 (33 it 0dgts) 40min 15508983.2 175.47
storm2.125 15512090.180
storm2.1000 15802589.698
-----------------------------------------------------------------
SGPF
sgpf3y3 -2967.91
sgpf3y4 -3994.18
sgpf3y5 -5172.07
sgpf3y6 -6463.24
sgpf5y3 -3027.706 -3027.62259 0.88
sgpf5y4 -4031.391 -4031.30455 6.35
sgpf5y5 -5201.282 -5201.19902 60.28
Bender's decomposition using SP/OSL
Courtesy of Alan King, IBM Corp.
Algorithm description
SP/OSL uses Benders decomposition to solve large deterministic equivalent stochastic programs.
In the following, PCx is a public domain Predictor-Corector code under
Test conditions
The first time reported below used serial SP/OSL Bender's decomposition split at the
4th period, with the cut nodes split into 120 subproblems of ``more or less'' equal
size. The second run uses parallel SP/OSL on an IBM SP-2 (each node a RS/6000-590)
where the nodes are accumulated into 100 subproblems of more or less equal size using
a depth-first accumulation strategy. Full primal and dual solutions are obtained.
The problems were solved to a relative optimality gap of 10^-16.
Results
Machine Memory Root Cycles Run Tme Opt Value
------- ------ ----------- -------- ---------
RS/6000-590 256MB 2 116.5sec -6479.034
4-node SP2 256MB/node 2 84sec -6480.081
Nested Bender's decomposition using ND-UM
Courtesy of Chris Donohue, Univ. of Michigan
Algorithm description
Test conditions
Results
Nested Bender's decomposition using MSLIP-OSL
Courtesy of Giorgio Consigli, University of Essex
Algorithm description
MSLIP-OSL is an adaptation of Gassmann's MSLIP where each node is solved using OSL, v.2.
Test conditions
All problems reported below were solved using an IBM RS/6000 model 590. Solution accuracies
are 10^-6.
Results
Readin Solution Output Opt Root
Problem Rep. Obj Time Time Time EVPI(%) Cuts Cuts
-------------------------------------------------------------------------
SGPF3y3 -2967.91 0.14 0.27 0.38 4.4 30 2
SGPF3y5 -7172.07 1.65 46.46 35.29 4.3 3
SGPF3y6 -6463.22 8.98 1051.7 294.93 6 5264 4
SGPF5y3 -3027.6 0.2 0.47 0.62 11.1 30 2
SGPF5y4 -4031.3 0.52 2.92 5.04 10.9 155 2
SGPF5y5 -5201.2 2.13 46.85 43.34 10.8 780 2
SGPF5y6 -6484.47 11.08 891.09 305.4 12.3 3905 2
Regularized Decompositions Method
Courtesy of Andrzej Ruszczynski, International
Institute for Applied Systems Analysis, Laxenburg, Austria
and
Artur Swietanowski
(Institute of Control and Information Engineering,
Warsaw University of Technology, Poland).
Algorithm description
The regularized decomposition method combines the ideas of
Benders decomposition and bundle methods for nonsmooth optimization.
The master techniques in the current implementation involve:
crash, critical scenarios and adaptive regularization.
The subproblem solver uses a penalty based restarting
variant of the primal simplex algorithm, which can start from any
combination of a nonsingular basis and a primal feasible solution.
It allows more freedom in modeling (random costs, bounds, etc..)
and quick hot starts within the decomposition method.
Test conditions
The tests were conducted on a single processing node of an 8-processor
shared memory CRAY 6400 SuperServer. Each processing node is equipped with a
Sparc processor roughly equivalent to a SparcStation 5 CPU. The code is
entirely sequential. All times are given in CPU seconds as measured by the
"times()" function.
Results
A large portion of the simplex iterations are so called `simple' iterations,
i.e. those that do not require a basis change. They occur whenever a non-
basic variable moves between its bounds without entering the basis.
In all the tests the feasibility and optimality tolerances in the subproblems
and cut tolerance in the master were equal to 1.0e-8.
Problem | Scen.|Master| Simplex iterations | Total
| num.|iter | total | simple | time
--------|-------|------|-----------|-----------|--------
fxm2 | 6 | 10 | 814 | 332 | 7.6
| 16 | 11 | 1,462 | 776 | 14.1
pltexpA2| 6 | 7 | 941 | 472 | 5.3
| 16 | 7 | 2,490 | 1,270 | 7.1
ssn | 10 | 21 | 9,789 | 6,889 | 19.1
| 50 | 41 | 118,546 | 88,612 | 216.3
| 100 | 34 | 234,637 | 171,019 | 427.4
| 500 | 95 | 2,344,477 | 1,990,404 | 3837.0
| 1000 |110 | 5,388,854 | 4,633,726 | 8575.3
storm | 10 | 18 | 4,212 | 1,735 | 30.8
| 50 | 33 | 24,389 | 13,196 | 171.2
| 100 | 33 | 47,427 | 27,234 | 326.2
| 500 | 42 | 250,992 | 163,615 | 1851.7
| 1000 | 43 | 506,109 | 329,234 | 3834.9
stormG2 | 8 | 21 | 3,850 | 1,576 | 26.4
| 27 | 25 | 12,724 | 5,430 | 83.2
| 125 | 36 | 61,955 | 32,775 | 443.4
| 1000 | 37 | 489,147 | 317,413 | 3389.2
This page written by Derek Holmes and John Birge. It was last modified on . Send
questions to
jrbirge@northwestern.edu
.