The following problems were solved using nested Benders decomposition with single cuts, using fast-back-fast-forward. The subproblems were solved using CPLEX 6.5 Note that we only know that we only have the optimal solution for the first stage when the program exits. For problems with more than three stages, the last two stages where aggregated. All problems are solved on a Sun Ultra 10, having 256Mb of memory, and a UltraSparcIIi processor with a clock speed of 300Mhz The times given are the solution times (system + user time) , excluding readin and setup, and excluding deallocation and printout. Problem Rows Columns Opt. Obj. Value Sol. time Opt cuts Feas. cuts Max res. mem. (Kbytes) ------------------------------------------------------------------------------------------------------------- pltexpA2_6 686 1820 -9.479354 0.04 1 0 2664 pltexpA2_16 1726 4540 -9.663308 0.05 1 0 2760 pltexpA3_6 4430 11612 -13.969368 0.16 7 0 4248 pltexpA3_16 28350 74172 -14.267458 0.77 17 0 8120 pltexpA4_6 26894 70364 -19.599417 0.58 7 0 6056 pltexpA4_16 454334 1188284 -18.849337 5.67 17 0 27880 pltexpA5_6 161678 422876 -23.214071 2.81 43 0 20360 pltexpA6_6 970382 2537948 -28.134408 14.54 259 0 106944 pltexpB3_6 1934 5084 -13.643226 0.14 7 0 4344 pltexpB4_6 4430 11612 -17.928191 0.23 7 0 4672 pltexpB5_6 9422 24668 -23.843400 0.41 19 0 7880 fxm2_6 1520 2172 18417.065572 0.53 13 22 3312 fxm2_16 3900 5602 18416.759028 0.61 13 22 3384 fxm3_6 6200 9492 18616.036163 1.83 57 123 5624 fxm3_16 41340 64162 18438.995076 4.75 149 206 10344 fxm4_6 22400 30732 18616.327973 3.37 57 123 6832 fxm4_16 386940 517282 18438.995076 25.38 149 206 22336 stormG2_8 4409 10193 15535235.730145 3.87 32 0 3816 stormG2_27 14441 34114 15508982.305507 10.98 39 0 4248 stormG2_125 66185 157496 15512091.184793 56.50 59 0 6504 sgpf5y3 1952 2509 -3027.603500 0.09 10 0 3592 sgpf5y4 9827 12384 -4031.303083 0.29 11 0 4232 sgpf5y5 49202 61759 -5201.196820 1.37 56 0 10480 sgpf5y6 246077 308634 -6484.465358 5.44 185 0 37312 sc2052r.4 101 102 -60.422961 0.02 1 2 2352 sc2052r.8 189 190 -60.422961 0.01 1 2 2352 sc2052r.16 365 366 -55.387714 0.02 1 5 2368 sc2052r.27 607 608 -15.105740 0.03 1 4 2336 sc2052r.32 717 718 -55.387714 0.04 1 9 2344 sc2052r.50 1113 1114 -30.764114 0.03 1 4 2352 sc2052r.64 1421 1422 -55.387714 0.03 1 9 2392 sc2052r.100 2213 2214 -10.070493 0.03 1 3 2384 sc2052r.200 4413 4414 -10.070493 0.05 1 3 2456 sc2052r.400 8813 8814 -10.070493 0.09 1 3 2608 sc2052r.800 17613 17614 -10.070493 0.17 1 3 2896 sc2053r.4 79 80 -60.422961 0.02 3 4 2440 sc2053r.8 123 124 -60.422961 0.02 3 4 2472 sc2053r.16 365 366 -55.387714 0.07 17 21 3568 sc2053r.27 343 344 -15.105740 0.03 4 10 2600 sc2053r.32 717 718 -55.387714 0.13 33 41 4768 sc2053r.50 585 586 -30.764114 0.04 3 10 2496 sc2053r.64 1421 1422 -55.387714 0.23 65 73 7136 sc2053r.100 1157 1158 -10.070493 0.06 5 13 2720 sc2053r.200 2257 2258 -10.070493 0.06 5 13 2752 sc2053r.400 4457 4458 -10.070493 0.10 5 13 2808 sc2053r.800 8901 8902 -10.070493 0.18 9 21 3344 The conditions for this case is the same as above, but we add one cut per 50 subproblems. Problem Rows Columns Opt. Obj. Value Sol. time Opt cuts Feas. cuts Max res. mem. (Kbytes) ------------------------------------------------------------------------------------------------------------- stormG2.1000 528185 1259121 15802590.244477 234.21 520 0 27488 The following problems were solved using nested Benders decomposition with single cuts, using fast-back-fast-forward. The subproblems were solved using CPLEX 6.5 We use a depth-first search of the tree, and delete all information from stages 4 and up when a branch of the subtree has been solved. The last two stages has been aggregated. All problems are solved on a Sun Ultra 10, having 256Mb of memory, and a UltraSparcIIi processor with a clock speed of 300Mhz Problem Rows Columns Opt. Obj. Value Sol. time Opt cuts Feas. cuts Max res. mem. (Kbytes) -------------------------------------------------------------------------------------------------------------------- pltexpA5_16 7270078 19014076 -23.896137 87.47 273 0 96000 pltexpA6_16 116321982 304226748 -28.431841 976.56 4369 0 135144 pltexpA7_6 5822606 15228380 -32.277880 93.120 1555 0 39744 The conditions for this case is the same as the one above, but the problem is solved on an Ultra Enterprise 450 with 2 UltraSparcIII processors, running at 750Mhz (although the code is single threaded). The load of the machine varied during the test, as this problem was not the only one run. the last two stages has been aggregated Problem Rows Columns Opt. Obj. Value Sol. time Opt cuts Feas. cuts Max res. mem. (Kbytes) ------------------------------------------------------------------------------------------------------------- pltexpA7_16 1861152446 4867629500 -32.821885 8690.95 69905 0 837656