This test problem suite consists of data and computational results for 12 two-stage stochastic integer programs arising in dynamic capacity acquisition and allocation applications. The problem formulation is described in [1]. The problems have mixed-integer first-stage variables, pure binary second-stage variables, and discrete distributions.
DATA:
The following table presents the sizes of the deterministic equivalents for each of the 12 problems instances and links to the data files. Columns NS, Rows, Cols, Bins, and Nonz refers to the number of scenarios, rows, columns, binary variables, and non-zero elements respectively. The data for the problems is organized into 4 zipped files. Each file includes SMPS data for three problem instances corresponding to three scenario numbers (200,300,500). The core files are provided in both MPS as well as the CPLEX LP format (.lp extension).
____________________________________________________________________________
Name NS Size of the Det. Eq. Data Rows Cols Bins Nonz dcap233_200 200 3012 5418 5406 10230 dcap233_300 300 4512 8118 8106 15330 dcap233.zip dcap233_500 500 7512 13518 13506 25530 dcap243_200 200 3612 7218 7206 13230 dcap243_300 300 5412 10818 10806 19830 dcap243.zip dcap243_500 500 9012 18018 18006 33030 dcap332_200 200 2412 4818 4806 9627 dcap332_300 300 3612 7218 7206 14427 dcap332.zip dcap332_500 500 6012 12018 12006 24027 dcap342_200 200 2812 6418 6406 12427 dcap342_300 300 4212 9618 9606 18627 dcap342.zip dcap342_500 500 7012 16018 16006 31027______________SOLUTION:
The following table presents the best known upper and lower bounds obtained with a specialized decomposition based branch & bound (DBB) algorithm (described in [1] and [2]), and that obtained by solving the deterministic equivalent MIP using the CPLEX 7.5 MIP solver (with default options). A CPU time limit of 1800 secs and a termination tolerance of 0.01% relative optimality gap was used. The computations were performed on a Sun Ultra 60 workstation with 512 MB RAM and a 480MHz processor.
____________________________________________________________________________________________________________________________
| DBB Algorithm | CPLEX 7.5 | Iter Nodes LB UB % Gap CPUs | Iter Nodes LB UB % Gap CPUs dcap233_200 | 343 687 1834.868 1834.893 0.0014 18.15 | 2263792 92397 1823.8912 1854.8395 1.6968 1802.68 dcap233_300 | 128 257 1644.342 1644.504 0.0098 10.25 | 1476305 19222 1623.1511 1657.1376 2.0939 1801.00 dcap233_500 | 124 249 1737.719 1737.728 0.0005 15.89 | 621088 36565 1712.0552 1748.6441 2.1371 1802.48 dcap243_200 | 331 663 2322.721 2322.721 0.0000 51.68 | 468340 103803 2299.1849 2352.5774 2.3222 1802.95 dcap243_300 | 100 201 2559.297 2559.545 0.0097 23.48 | 190918 73342 2541.5712 2640.6479 3.8982 1802.47 dcap243_500 | 231 463 2167.512 2167.512 0.0000 83.84 | 420752 21677 2128.5289 2197.3689 3.2342 1801.93 dcap332_200 | 1754 3509 1060.676 1060.781 0.0100 133.34 | 350650 151932 1059.4573 1061.1722 0.1619 1802.63 dcap332_300 | 1270 2541 1253.040 1253.082 0.0033 141.32 | 320464 94357 1251.0195 1257.7704 0.5396 1803.20 dcap332_500 | 1155 2311 1588.717 1588.876 0.0100 199.67 | 765243 35132 1587.6687 1590.7464 0.1939 1801.93 dcap342_200 | 462 925 1619.531 1619.654 0.0076 131.94 | 390094 113059 1619.2613 1620.9507 0.1043 1802.62 dcap342_300 | 980 1961 2067.777 2067.818 0.0020 439.15 | 429196 59446 2066.9391 2071.3888 0.2153 1802.69 dcap342_500 | 510 1021 1904.722 1904.803 0.0043 349.98 | 679448 14831 1903.7113 1913.4352 0.5108 1801.23
REFERENCES:
[1] S. Ahmed and R. Garcia. "Dynamic Capacity Acquisition and Assignment under Uncertainty," Annals of Operations Research, vol.124, pp. 267-283, 2003.
[2] S. Ahmed, M. Tawarmalani, and N. V. Sahinidis. "A Finite Branch and Bound Algorithm for Two-stage Stochastic Integer Programs,'' Mathematical Programming , vol.100, pp.355-377, 2004.