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.