A (PO)rtable (S)tochastic programming (T)est (S)et (POSTS)

Derek Holmes, Cargill Financial Services (formerly University of Michigan)

What is POSTS?

POSTS is a small test set of stochastic programming recourse problems (SLP) designed to highlight different qualities of general linear recourse problems. This test set is meant as a common test bed for reporting the computational characteristics of state-of-the-art SLP algorithms and their implementations. The problems are generally extendible to an arbitrary number of periods and scenarios. Each is given in standard SMPS format (Birge, at. al.). Go Back to Contents

How to get POSTS

The POSTS test set is available as a zip file, posts.zip, or a compressed tar file posts.tar.Z. To uncompress the files, type (from a UNIX prompt) either

unzip posts.zip

for the zip file or

zcat posts.tar.Z | tar -xvf -

Instructions and solution values are in README files in each package. Go Back to Contents

How should the problems be solved?

To further "standardize" any computational results that may be reported using POSTS, we suggest using the following guidelines:

Tolerances and solutions
- All stages should be solved to a relative tolerance of 10^(-6), i.e. if UB and LB are upper and lower bounds on the recourse objective in any given stage, (UB-LB)/(|LB|+0.1) <= 10^(-6). Interior point codes should use the same tolerance, but are not required to provide a basic solution.
- Primal and dual solutions should be given for all nodes in the solution tree. (If not, at least primal solutions should be given, and the absence of dual solutions should be reported.)
Reporting
- Complete descriptions of the hardware and software used should be given, including machines make, model, memory, and speed (if applicable). If parallel codes are used, some indication of processor-processor bandwidth and message latency should be reported. (Ideally, the guidelines presented in Section 7 of Barr and Hickman should be followed.) If external routines are used (e.g. LP solvers), they should be cited.
- Both algorithmic solution times and total times should be reported. Algorithmic solution times exclude input, problem set-up, and output. System times should be used if uniprocessor codes are used. If a parallel code is being used, the best and average wall clock times over a group of tests should be used. Using machines loaded with other processes should be avoided, if possible.

Any suggestions or comments would be GREATLY appreciated, and can be forwarded to jrbirge@northwestern.edu . Go Back to Contents

Problem Descriptions

Here is a summary of the problems in the set. For more detailed descriptions, (and descriptions of more problems) Click here!.

Costs and RHS stochastic, time dependent scenarios. The only problems not arbitrarily created from those with only RHS stochasticity are the SGPF problems submitted courtesy of Prof. Karl Frauendorfer. The SGPF problems arise from a portfolio management application approximated with his discrete barycentric approximation system. (Frauendorfer, 1992). There is a set of small size problems and a set of large size problems publicly available. Due to their excessive size, only the smaller set will be used. The problems in the set and their filenames are given in the table below.

        Stages   Scenarios     Cor            Time        STOCH
      ---------------------------------------------------------------

          3          25      sgpf3y3.cor  sgpf3y3.tim  sgpf3y3.sce
          4         125      sgpf3y4.cor  sgpf3y4.tim  sgpf3y4.sce
          5         625      sgpf3y5.cor  sgpf3y5.tim  sgpf3y5.sce
          6        3125      sgpf3y6.cor  sgpf3y6.tim  sgpf3y6.sce

RHS random: Finding feasibility The most tightly constrained problem in the test set is SCFXM1, which is tightly coupled in at least the first few stages. (See note below) The problem first appeared in Ho and Loute. There are 2,3, and 4 stage versions of this problem, and 2 and 16 scenarios per stage STOCH versions. The problems and their descriptions are given below

        Stages  Scens/stage    Cor      Time      STOCH
      ----------------------------------------------------

          2          6       fxm.cor  fxm2.tim  fxm2_6.sto
                    16                          fxm2_16.sto

          3          6       fxm.cor  fxm3.tim  fxm3_6.sto
                    16                          fxm3_16.sto

          4          6       fxm.cor  fxm4.tim  fxm4_6.sto
                    16                          fxm4_16.sto

Note: The period partitions in the core file are different from those originally used in Gassman 1988. The original fxm file from the netlib test set was partitioned so as to have roughly equal size blocks.

RHS random: A moderate number of optimal bases. A problem with a relatively few number of optimal second stage bases is the PLTEXP problem (Sims), which is the linear relaxation of a stochastic capacity expansion problem. The problem is extendable to an arbitrary number of stages and an arbitrary number of scenarios.

Thick tree version. This test set has either 6 or 16 scenarios per stage. The associated file names are shown below

     Stages  Scens/stage    Cor             Time       STOCH
    ---------------------------------------------------------------

       2          6       pltexpA2.cor  pltexpA2.tim  pltexpA2_6.sto
                 16                                   pltexpA2_16.sto

       3          6       pltexpA3.cor  pltexpA3.tim  pltexpA3_6.sto
                 16                                   pltexpA3_16.sto

       4          6       pltexpA4.cor  pltexpA4.tim  pltexpA4_6.sto
                 16                                   pltexpA4_16.sto

       5          6       pltexpA5.cor  pltexpA5.tim  pltexpA5_6.sto
                 16                                   pltexpA5_16.sto

       6          6       pltexpA6.cor  pltexpA6.tim  pltexpA6_6.sto

Thin tree version. This test set has 6 scenarios in the first stage, and two scenarios per stage thereafter. These problems are provided as a contrast with those in (4.1), and may show results less dependent on subproblem solution.

     Stages  Scens in Stg 2   Cor             Time       STOCH
    ---------------------------------------------------------------

       3          6       pltexpA3.cor  pltexpA3.tim  pltexpB3_6.sto

       4          6       pltexpA4.cor  pltexpA4.tim  pltexpB4_6.sto

       5          6       pltexpA5.cor  pltexpA5.tim  pltexpB5_6.sto

RHS random: Huge number of optimal bases. Due to its size and the high dimension of its support, STORM (Mulvey and Ruszczy/'{n}ski, 1992) is a problem well known for its difficulty. The problem as originally received was a very large two-stage only problem, with dim (Supp) = 118. Prof. H.I. Gassmann modified the model by enforcing some dependence among the RHSs. These instantiations form the basis of this test set. However, in the spirit of the original model, the smaller two-stage model has extended to include up to 1000 scenarios.

        Stages   Scenarios    Cor         Time           STOCH
      -------------------------------------------------------------

          2          8    stormG2.cor  stormG2.tim   stormG2_8.sto
                    27                               stormG2_27.sto
                   125                               stormG2_125.sto
                  1000                               stormG2_1000.sto

References (please excuse the varied styles)

J. R. Birge, M.A.H. Dempster, H. I. Gassman, E. A. Gunn, A. J. King, and S. W. Wallace, 1987. ``A Standard forinput format for multiperiod stochastic linear programs,'' COAL newsletter, 17, pp. 1-20.
K. Frauendorfer, Lecture Notes in Economics and Mathematical Systems No 392, Stochastic Two-Stage Programming (Springer-Verlag, Berlin, 1993).
H. I. Gassman, 1990. ``MSLiP: A computer code for the multistage stochastic linear programming problem.'' Mathematical Programming, 47, pp. 407-423.
J. K. Ho, 1975. ``Optimal Design of Multistage Structures: A Nested Decomposition Approach,'' Computers and Structures, Vol. 5, pp 249-255.
M. J. Sims, 1992. ``Use of a stochastic capacity planning model to find the optimal level of flexibility for a manufacturing system,'' Senior Design Project, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109.
J. M. Mulvey, and A. Ruszczynski, 1992. ``A New Scenario Decomposition Method for Large Scale Stochastic Optimization,'' Technical Report SOR-91-19, Dept. of Civil Engineering and Operations Research, Princeton Univ. Princeton, N.J. 08544

>Go Back to Contents

Problem sizes and solutions

This table describes the characteristics of the stochasticity for each problem, as well as the size of the Deterministic Equivalent and the optimal objective value.

                                 Det. Equiv.
Problem    Stages  Scen/Stage  Rows   Columns  Total Scen. Opt. Obj. Value
-------------------------------------------------------------------------
PLTEXP
pltexpA2_6    2       6         686     1856         6        -9.479354
pltexpA2_16   2      16        1726     4636        16        -9.663308
pltexpA3_6    3       6        4430    11864        36       -13.969368
pltexpA3_16   3      16       28350    75804       256       -14.267458
pltexpA4_6    4       6       26894    71912       216       -19.599417
pltexpA4_16   4      16      454334  1214492      4096       -18.849337
pltexpA5_6    5       6      161678   432200      1296       -23.214073
pltexpA6_6    5       6      970382  2593928      7776       -28.134408
pltexpB3_6    3     6+1+1                            6       -13.643226
pltexpB4_6    3     6+1+1+1                          6       -17.928191
pltexpB5_6    3     6+1+1+1+1                        6       -23.846166
-------------------------------------------------------------------------
SCFXM
fxm2.6        2       6         780     1047         6      18416.686
fxm2.16       2      16        1680     2227        16      18416.655
fxm3.6        3       6        4020     5295        36      18615.932
fxm3.16       3      16       24720    32435       256      18438.891
fxm4.6        4       6       23460    30783       216      18616.224
fxm4.16       4      16      393360   515763      4096      18438.891
-------------------------------------------------------------------------
STORM
stormG2.8      2       8        2985    11456         8      15535231.897
stormG2.27     2      27        9635    37809        27      15508982.306
stormG2.125    2     125       43935   173735       125      15512090.180
stormG2.1000   2    1000      350185  1387360      1000      15802589.698
-------------------------------------------------------------------------
SGPF
sgpf3y3       3       5        1220     1595        25        -2967.917
sgpf3y4       4       5        6097     7974       125        -3994.198
sgpf3y5       5       5       30487    39868       625        -5172.165
sgpf3y6       6       5      152434   199341      3125        -6463.323
sgpf5y3       3       5        1282     1342        25        -3027.706
sgpf5y4       4       5        5657     5726       125        -4031.391
sgpf5y5       5       5       24407    24476       625        -5201.282
sgpf5y6       6       5      246077   308733      3125        -6479.614

Go Back to Contents

This page was last modified on . Send questions to jrbirge@northwestern.edu.