Computational Results

Go back to Contents Page.

Contents

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.

Technical Report Current Trends in Stochastic Programming Computation and Applications[Postscript]

John. R. Birge

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 .