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

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

Contents

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: 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)

    >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.