supplementary file)

1
Supplementary Material to “Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse”
Detailed Computational Results
Summary Tables
Table 1 Comparison of algorithms for CAP instances when Cplex cuts are on. Times are
given in seconds. At each (K,CAP #) row, the averages of four instances are reported.
K
CAP #
Avg Time (# unsolved)
EXT
BEN
MP
SP
250
101-104
111-114
121-124
131-134
Mean
258
2359
4718(2)
4151(1)
1858
(4)
(4)
(4)
(4)
-
(4)
(4)
(4)
(4)
-
61
333
1104
468
319
500
101-104
111-114
121-124
131-134
Mean
1171
10787(3)
10935(3)
9512(3)
6020
(4)
(4)
(4)
(4)
-
(4)
(4)
(4)
(4)
-
149
957
4738(1)
1527
1008
Avg Gap (%)
BEN
MP
SP
0.00
0.00
0.43
0.19
0.16
14.02
7.88
15.61
20.04
14.39
14.15
8.28
16.62
21.93
15.25
0.00
0.00
0.00
0.00
0.00
0.00
2.00
3.12
1.44
1.64
15.04
7.87
15.76
20.81
14.87
14.53
7.81
17.51
22.29
15.53
0.00
0.00
0.09
0.00
0.02
EXT
Table 2 Number of nodes processed in different methods for CAP instances. At each
(K,CAP #) row, the geometric means of four instances are reported. “>” means that there
are some instances that couldn’t be solved in the time limit of four hours in a category,
therefore we only have a lower bound on the number of nodes.
Without Cplex Cuts
BEN
MP
SP
With Cplex Cuts
BEN
MP
SP
K
CAP #
EXT
250
101-104
111-114
121-124
131-134
Mean
1
1
>1
>7
2
>8336
>6736
>3936
>6226
6091
>8293
>5531
>3455
>4706
5226
3
339
1342
34
81
>8834
>5937
>4229
>8238
6538
>8766
>6012
>3677
>6958
6060
2
141
706
39
52
500
101-104
111-114
121-124
131-134
Mean
1
>1
>1
>1
1
>3814
>3123
>1594
>2687
2672
>4108
>2454
>1836
>2467
2599
4
>1515
>2322
71
174
>3909
>2763
>1570
>3903
2852
>4606
>2768
>1894
>3076
2936
4
394
>2067
74
125
2
Table 3 Number of nodes processed in different methods for SNIP instances. At each
(K,CAP #) row, the geometric means of four instances are reported. “>” means that there
are some instances that couldn’t be solved in the time limit of four hours in a category,
therefore we only have a lower bound on the number of nodes. “K” represents thousand.
Without Cplex Cuts
BEN
MP
SP
With Cplex Cuts
BEN
MP
SP
snipno
Budget
EXT
3
30
40
50
60
70
80
90
Mean
>1
>1
>1
>1
>1
>1
>1
1
289K
>3925K
>3423K
>3303K
>4467K
>4800K
>3718K
2691K
58K
>960K
>556K
>658K
>1770K
>1293K
>1666K
>693K
25K
496K
314K
>302K
>903K
>1833K
>2387K
465K
13K
247K
85K
179K
315K
488K
1225K
191K
11K
199K
88K
110K
165K
>465K
>991K
148K
1772
25K
15K
38K
34K
65K
373K
30K
4
30
40
50
60
70
80
90
Mean
>1
>1
>1
>1
>1
>1
>1
1
201K
569K
>755K
>890K
>1254K
710K
>747K
654K
34K
141K
160K
>225K
>330K
>146K
>113K
138K
11K
47K
73K
94K
45K
26K
104K
46K
7488
15K
28K
36K
33K
3796
18K
16K
5417
15K
28K
50K
44K
18K
>65K
25K
972
2007
2873
7073
5109
740
2983
2391
Full Tables
Table 4 Relaxation gap (%) for CAP instances with 250 scenarios.
CAP #
BEN
MP
PR-CGLP
SP
SP-CGLP
101
102
103
104
111
112
113
114
121
122
123
124
131
132
133
134
17.45
21.88
24.45
25.81
9.02
8.98
8.50
8.38
15.89
19.03
20.14
20.64
20.55
25.22
27.13
28.03
15.68
20.31
22.56
24.42
8.68
8.54
7.91
6.92
15.14
18.31
19.53
20.07
19.44
24.05
26.02
27.20
13.64
17.49
20.01
20.86
8.06
8.04
7.52
7.54
13.65
16.47
17.32
17.84
17.35
21.65
23.22
24.04
0.03
0.11
0.10
0.04
0.04
0.33
0.46
0.81
0.18
0.78
1.11
1.89
0.02
0.22
0.36
0.60
0.00
0.00
0.11
0.33
0.05
0.20
0.11
0.53
0.03
0.60
1.38
2.59
0.01
0.94
1.87
3.03
3
Table 5 Effect of Cplex cuts on average % root gap obtained by different methods for CAP
instances with 250 scenarios.
CAP #
101
102
103
104
111
112
113
114
121
122
123
124
131
132
133
134
Without Cplex Cuts
BEN
MP
SP
With Cplex Cuts
BEN
MP
SP
17.45
21.88
24.45
25.81
9.03
8.98
8.50
8.38
15.99
19.03
20.20
20.65
20.55
25.22
27.14
28.03
12.78
16.52
18.63
19.70
8.43
8.32
7.76
6.86
15.93
17.01
20.18
18.86
16.01
20.19
21.98
22.42
16.31
21.06
23.79
25.16
9.01
8.80
8.18
7.12
17.65
18.88
22.96
20.67
20.73
25.97
26.73
27.77
0.03
0.11
0.10
0.06
0.04
0.33
0.46
0.82
0.18
0.79
1.24
1.89
0.05
0.22
0.40
0.66
12.68
16.37
18.43
19.28
8.45
8.30
7.68
6.72
17.65
17.02
22.93
20.68
17.11
25.46
21.81
22.32
0.03
0.10
0.10
0.06
0.04
0.33
0.46
0.82
0.18
0.78
1.24
1.89
0.05
0.22
0.40
0.66
4
Table 6 Comparison of algorithms for CAP instances. For solved instances, solution times
are reported in seconds. For unsolved instances, optimality gap percentages are reported in
bold.
Without Cplex Cuts
BEN
MP
SP
With Cplex Cuts
BEN
MP
SP
104
247
358
482
1004
2869
3320
3240
625
3824
0.88
0.85
631
3221
10143
0.76
11.23
15.41
16.91
16.16
7.86
7.84
8.13
8.25
13.78
18.19
15.29
17.19
18.95
22.76
23.59
23.58
12.66
15.28
16.98
15.46
9.06
8.20
7.73
7.51
17.38
17.19
16.37
14.95
21.64
25.20
23.04
23.04
57
73
66
60
172
295
597
3901
258
1912
1684
9807
243
612
621
561
11.14
14.39
15.09
15.45
8.81
8.65
7.71
6.35
14.80
16.26
14.84
16.52
17.64
21.30
21.00
20.23
12.20
14.34
14.84
15.23
8.87
9.33
7.59
7.34
17.64
17.10
17.35
14.41
20.33
25.16
20.72
21.52
56
71
58
58
160
260
569
518
268
635
1232
7079
242
439
617
730
432
1082
1837
2187
4534
0.12
3.38
4.49
4789
1.73
4.93
5.82
2742
0.12
1.70
3.95
12.76
18.27
17.92
18.04
9.46
8.58
8.69
7.33
15.82
17.39
16.37
15.96
19.26
24.01
24.44
23.95
12.20
17.54
18.53
17.21
9.14
8.35
6.89
7.62
20.35
18.98
15.49
17.19
19.66
25.78
25.52
25.08
134
163
228
188
607
1076
0.19
8266
1215
6866
0.33
0.19
646
1398
1932
1350
11.90
15.47
15.64
17.16
9.44
7.79
6.72
7.52
14.51
17.18
16.35
15.00
19.04
22.16
20.39
21.65
11.42
15.31
15.66
15.71
9.18
7.87
7.28
6.92
17.70
17.87
17.28
17.19
19.49
25.69
22.07
21.90
113
138
202
158
556
751
1601
1255
792
3457
0.35
12811
775
1798
2283
1709
K
CAP #
EXT
250
101
102
103
104
111
112
113
114
121
122
123
124
131
132
133
134
500
101
102
103
104
111
112
113
114
121
122
123
124
131
132
133
134
5
Table 7 Relaxation gap (%) for SNIP instances
Budget
Inst.
30
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
40
50
60
70
80
90
snipno = 3
BEN
MP
SP
snipno = 4
BEN
MP
SP
22.3
22.1
22.5
22.6
22.9
25.3
26.7
25.5
26.7
27.0
26.9
28.5
27.0
25.9
29.4
26.9
28.6
28.6
27.1
29.6
29.0
28.6
28.8
28.4
29.7
28.9
31.4
30.9
31.7
31.5
31.0
34.2
33.0
33.4
33.8
25.0
24.6
25.3
25.3
25.5
27.6
28.5
27.4
28.9
29.9
30.6
30.4
31.0
28.6
32.3
32.0
32.1
31.7
29.5
34.9
33.0
31.4
32.0
31.9
34.8
33.5
32.7
32.9
32.4
34.9
33.9
35.7
35.8
36.8
38.6
13.1
13.2
11.4
15.8
14.2
18.1
19.0
15.7
16.3
21.1
19.5
20.8
16.6
16.7
19.0
17.0
21.1
19.0
19.3
19.2
21.3
19.5
17.8
21.1
22.2
18.3
22.4
22.9
22.6
23.2
23.0
23.9
23.2
23.2
24.5
8.0
8.1
7.6
8.1
7.8
11.0
12.3
9.8
11.5
12.1
12.0
13.5
11.1
9.6
13.9
11.4
13.3
12.3
11.8
13.5
12.7
12.4
12.3
12.0
13.7
12.1
14.4
15.1
15.3
15.6
15.0
18.7
18.5
17.4
18.6
11.3
15.2
12.7
13.7
15.3
15.5
18.0
15.6
18.4
17.2
24.0
19.4
19.7
14.7
21.0
21.1
23.1
22.0
21.8
23.4
24.9
22.8
20.4
24.1
27.1
24.2
23.7
22.9
23.9
28.1
27.5
27.3
29.4
28.0
33.6
7.9
8.6
8.1
8.7
8.1
10.8
11.8
10.1
11.5
12.8
14.5
13.5
13.4
10.5
14.0
15.6
15.0
14.1
12.0
16.8
15.4
11.6
13.3
13.6
15.4
15.3
12.5
15.7
12.8
15.3
16.6
16.0
19.9
19.1
20.5
6
Table 8 Effect of Cplex cuts on average % root gap obtained by different methods for SNIP
instances with snipno = 3.
Budget
Inst.
30
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
40
50
60
70
80
90
Without Cplex Cuts
BEN
MP
SP
With Cplex Cuts
BEN
MP
SP
22.5
23.6
22.8
24.1
22.9
28.7
28.2
25.6
26.7
27.0
27.3
28.7
27.5
25.9
29.6
26.9
28.8
29.3
27.2
29.6
29.1
28.7
28.9
28.6
29.8
29.0
31.4
30.9
32.8
31.6
31.2
34.2
33.1
33.4
33.9
4.97
7.04
3.75
5.51
4.61
8.86
10.59
5.09
5.73
6.57
7.43
7.65
5.79
4.08
7.94
5.19
7.18
8.70
3.48
6.08
6.84
5.35
5.27
4.28
5.34
5.82
7.23
6.08
9.21
6.30
5.77
8.67
8.49
8.84
8.99
12.5
13.7
12.8
14.1
13.2
16.5
18.3
15.4
16.4
18.6
18.9
20.7
16.7
15.2
20.0
16.9
19.5
19.2
17.3
19.7
19.8
18.6
18.0
18.5
21.2
17.6
22.7
20.2
22.5
20.8
21.6
26.1
23.1
23.4
24.6
11.8
14.2
11.8
13.9
11.9
13.6
17.5
14.6
16.0
16.9
15.6
18.5
15.1
14.6
18.5
15.1
19.7
16.4
15.1
17.7
17.9
17.7
17.3
16.5
18.1
16.8
17.8
18.4
19.8
18.6
18.7
21.4
21.9
20.9
21.4
4.71
4.53
4.22
5.21
4.54
5.17
7.54
4.87
6.85
7.93
6.70
7.54
4.74
4.24
7.50
5.34
6.36
6.17
3.23
6.22
6.42
4.71
4.13
3.65
5.17
4.17
7.24
5.68
6.63
6.63
5.55
9.64
7.60
7.92
8.56
3.36
3.28
2.56
3.60
3.45
4.92
6.07
4.30
5.79
6.42
5.19
7.04
4.31
3.14
6.66
4.08
6.46
4.91
3.72
5.76
5.52
4.13
4.00
3.51
4.41
4.37
5.32
5.19
5.83
5.18
6.17
7.84
7.47
7.50
7.31
7
Table 9 Effect of Cplex cuts on average % root gap obtained by different methods for SNIP
instances with snipno = 4.
Budget
Inst.
30
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
40
50
60
70
80
90
Without Cplex Cuts
BEN
MP
SP
With Cplex Cuts
BEN
MP
SP
25.4
24.9
25.8
27.3
25.6
28.9
30.2
27.6
29.2
30.0
31.4
31.6
31.5
28.6
34.1
33.5
32.4
31.8
29.6
35.0
33.1
31.7
32.4
32.3
35.0
33.8
32.9
32.9
32.4
35.0
35.6
36.4
36.1
36.9
38.8
3.91
4.38
5.19
6.92
4.46
9.15
10.63
4.33
6.53
6.79
8.67
8.54
6.50
3.22
13.74
11.56
9.22
5.77
3.33
10.67
8.25
4.64
5.95
6.13
6.92
6.74
3.77
4.09
3.42
4.67
6.61
7.26
6.67
7.21
8.45
12.5
14.9
14.3
14.7
14.6
15.5
17.8
15.7
17.8
21.5
18.6
20.8
19.6
16.5
21.1
22.7
22.2
21.0
19.4
24.5
23.4
21.3
20.7
22.6
24.4
24.0
21.9
23.2
23.7
25.6
24.6
24.1
26.4
27.6
30.9
12.1
14.4
12.6
15.0
13.1
15.2
17.2
15.0
16.9
16.0
17.8
17.7
18.5
16.4
19.7
19.7
20.2
17.9
16.4
22.8
19.9
17.0
18.7
17.5
22.1
18.8
19.0
18.5
17.8
18.9
18.1
21.6
23.3
25.3
23.8
3.56
4.76
4.66
5.02
5.74
4.26
6.42
4.66
7.38
9.23
7.67
8.29
6.20
3.21
8.19
10.11
8.24
6.13
4.24
10.48
8.49
3.53
5.31
5.78
8.32
8.86
4.62
5.75
4.10
7.72
7.13
7.58
8.27
10.37
12.57
2.65
2.11
3.20
3.84
3.62
3.72
4.59
2.72
5.51
5.55
6.55
6.26
5.16
2.92
6.74
7.72
6.64
4.94
2.87
8.54
6.28
2.93
3.53
4.19
6.58
4.85
2.18
2.58
2.49
3.02
3.17
5.31
6.10
6.58
7.21
8
Table 10 Comparison of algorithms for SNIP instances when Cplex cuts are off. For solved
instances, solution times are reported in seconds. For unsolved instances, optimality gap
percentages are reported in bold.
Budget
Inst.
EXT
snipno = 3
BEN
MP
30
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
18.2
17.2
18.8
16.4
19.4
21.3
22.4
21.0
23.9
36.6
23.5
20.5
23.0
26.0
37.6
24.4
19.1
25.5
25.0
24.7
23.0
20.3
26.9
29.3
36.0
25.1
26.3
31.0
23.6
38.4
25.8
27.0
32.9
27.7
40.2
338
794
666
955
624
1576
1.29
1.03
1.04
6598
4303
1.36
3.26
3716
1.70
3110
3.57
3.96
1.45
2.94
3.51
4.14
4.02
4.43
3.40
1.94
4.70
5.69
4.04
3.32
3.85
7.04
7.28
6.41
6.12
40
50
60
70
80
90
283
913
419
790
321
1238
0.85
11145
11409
4258
1294
2.35
11107
2486
8437
1940
1.27
3.89
7800
4930
0.93
1.81
2.60
1.67
1.28
6834
4.89
2.63
4.68
10784
4.74
6.20
3.60
2.82
3.42
SP
EXT
snipno = 4
BEN
MP
361
536
455
468
413
748
3599
4277
2545
1983
1322
8424
2019
625
4865
914
1877
0.71
1103
3074
3486
4899
1.11
2656
2627
2440
0.88
2.07
0.48
1.38
1.86
2.47
2.00
9618
2.47
19.4
20.1
24.9
26.1
21.7
22.6
26.5
22.9
29.4
27.2
26.6
26.7
28.9
30.8
32.2
29.3
25.9
31.5
33.3
31.5
43.4
31.6
44.3
32.1
43.7
41.0
35.3
40.0
31.8
100.0
46.9
48.9
50.3
47.7
100.0
303
771
850
835
472
439
1950
2330
2632
3619
1077
4587
1.94
1522
4463
2621
3703
2.69
1560
13187
2943
3336
4.89
7223
1.16
3931
4049
6112
3895
4884
1128
3615
2.09
8801
3.30
216
527
919
724
356
563
4599
1739
2878
5091
2933
6107
10484
1179
2652
5871
4151
1.52
2289
1.54
7827
13702
3.95
1.78
2.23
11174
4682
3.72
11756
3.41
9959
5.84
8.71
7.72
6.23
SP
401
493
510
546
489
480
980
662
908
980
931
1233
3530
502
1511
997
1007
3720
564
2956
1178
507
2028
1059
1238
904
617
1038
618
892
825
1028
5093
1723
1547
9
Table 11 Comparison of algorithms for SNIP instances when Cplex cuts are on. For solved
instances, solution times are reported in seconds. For unsolved instances, optimality gap
percentages are reported in bold.
Budget
Inst.
EXT
snipno = 3
BEN
MP
30
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
18.2
17.2
18.8
16.4
19.4
21.3
22.4
21.0
23.9
36.6
23.5
20.5
23.0
26.0
37.6
24.4
19.1
25.5
25.0
24.7
23.0
20.3
26.9
29.3
36.0
25.1
26.3
31.0
23.6
38.4
25.8
27.0
32.9
27.7
40.2
113
277
166
241
166
373
1941
553
673
1101
423
1039
556
149
972
357
1029
7740
495
433
5008
1998
1018
972
548
1281
4988
1537
3934
707
1783
13986
5680
6217
2874
40
50
60
70
80
90
236
270
279
435
222
330
6815
1426
4781
1038
678
3623
1186
403
1600
845
4329
6919
771
657
9155
2808
1208
999
779
1559
1.28
7345
0.95
996
3052
2.15
0.54
0.32
7289
SP
EXT
snipno = 4
BEN
MP
355
394
341
494
522
645
1077
691
866
950
755
1073
1114
423
1287
766
1290
3687
645
753
1579
1678
1187
1570
1048
1356
2124
1558
2330
938
1519
10119
2151
4426
7447
19.4
20.1
24.9
26.1
21.7
22.6
26.5
22.9
29.4
27.2
26.6
26.7
28.9
30.8
32.2
29.3
25.9
31.5
33.3
31.5
43.4
31.6
44.3
32.1
43.7
41.0
35.3
40.0
31.8
100.0
46.9
48.9
50.3
47.7
100.0
156
145
277
234
141
227
356
170
318
304
306
381
920
135
1011
630
366
792
136
909
623
282
266
716
920
418
127
211
149
264
215
220
274
390
743
241
243
489
367
247
369
1120
241
573
2338
1708
1703
1150
318
1986
3510
1005
1834
774
2814
3282
539
2748
1155
9146
3021
642
1719
1017
5817
2089
1.13
8750
3.98
2.63
SP
353
422
475
514
466
460
860
721
555
800
631
815
967
360
1080
896
673
875
579
1064
947
567
801
1115
1480
653
327
554
437
519
583
375
483
552
734