next up previous
Next: About this document ... Up: paper93 Previous: Bibliography

Appendix:Problem statistics and computational results


Table 1: Problem Statistics: Pure SDPs
NAME ROWS SDP LIN OPT VALUE
toruspm3-8-50 512 [1; 512] - 527.808663
toruspm3-15-50 3,375 [1; 3,375] - 3474.7939
torusg3-8 512 [1; 512] - 457.358179
torusg3-15 3,375 [1; 3,375] - 3134.5683
bm1 883 [1; 882] - 23.43982
biomedP 6,515 [1; 6,514] - 33.6 *
industry2 12,638 [1; 12,637] - 65.6 *
fap09 15,225 [1; 174] 14,025 10.8 *
fap25 2,244,021 [1; 2,118] 2,232,141 12.5 * (lb, not opt)
fap36 8,448,105 [1; 4,110] 8,405,931 63.7 * (lb, not opt)
fap-sup-25 322,924 [1; 2,118] 311,044 12.5 * (lb, not opt)
fap-sup-36 1,154,467 [1; 4,110] 1,112,293 63.7 * (lb, not opt)
hamming_9_8 2,305 [1; 512] - 224
hamming_10_2 23,041 [1; 1,024] - 102.4
hamming_11_2 56,321 [1; 2,048] - 170 2/3
hamming_7_5_6 1,793 [1; 128] - 42 2/3
hamming_8_3_4 16,129 [1; 256] - 25.6
hamming_9_5_6 53,761 [1; 256] - 85 1/3
copo14 1,275 $ [14; 14\times 14]$ 364 0
copo23 5,820 $ [23; 23\times 23]$ 1771 0
copo68 154,905 $ [68; 68\times 68]$ 50,116 0
truss5 208 $ [34; 33\times 10, 1]$ - 132.6356779
truss8 496 $ [34; 33\times 19, 1]$ - 133.1145891
hinf12 43 $ [3; 6, 6, 12]$ - - 0.0398 (?)
hinf13 57 $ [3; 7, 9, 14]$ - -45.476 (?)


Table 2: Problem Statistics: Mixed and Pure SOCPs
NAME ROWS SDP/QUADR LIN OPT VALUE
filter48 969 $ [1; 48]$/$ [1; 49]$ 931 1.416129
filtinf1 983 $ [1; 49]$/$ [1; 49]$ 945 primal inf.
minphase 48 $ [1; 48]$/- - 5.980989
nql30 3,680 -/ $ [900; 900\times 3]$ 3,602 -0.946028
nql60 14,560 -/ $ [3600; 3600\times 3]$ 14,402 -0.935423
nql180 130,080 -/ $ [32400; 32400\times 3]$ 129,602 -0.927717
qssp30 3,691 -/ $ [1891; 1891\times 4]$ 2 -6.496675
qssp60 14,581 -/ $ [7381; 7381\times 4]$ 2 -6.562696
qssp180 130,141 -/ $ [65341; 65341\times 4]$ 2 -6.639527
sched_50_50_orig 2527 -/[2;2474,3] 2,502 26,673
sched_100_50_orig 4844 -/[2;4741, 3] 5,002 181,889
sched_100_100_orig 8338 -/[2;8235, 3] 10,002 717,367
sched_200_100_orig 18087 -/[2;17884, 3] 20,002 141,360
sched_50_50_scaled 2526 -/2475 2,502 7.852038
sched_100_50_scaled 4843 -/4742 5,002 67.16628
sched_100_100_scaled 8337 -/8236 10,002 27.33145
sched_200_100_scaled 18086 -/17885 20002 51.81247
nb 123 -/ $ [793;793 \times 3]$ 4 - 0.050703
nb_L1 915 -/ $ [793;793 \times 3]$ 797 - 13.01227
nb_L2 123 -/ $ [839; 1 \times 1677, 838 \times 3]$ 4 -1.628972
nb_L2_bessel 123 -/ $ [839; 1 \times 123, 838 \times 3]$ 4 -0.102571


Table 3: CPU times in seconds, SOCP problems; MM: memory exceeded, TT: more than 35 hrs., parentheses: AMPL input
PROBLEM LOQO MOSEK SDPT3 SeDuMi
nb 56 17 42 31
nb_L1 (65) 20 79 38
nb_L2 61 39 83 44
nb_L2_Bessel 28 18 46 22
nql30 (114) 3 12 6
nql60 (1978) 20 66 33
nql180 (TT) 344 MM MM
qssp30 15 5 24 8
qssp60 151 31 180 109
qssp180 (TT) 531 MM MM
sched_50_50_orig 23 3 25 11
sched_100_50_orig 52 7 85 31
sched_100_100_orig 378 16 105 62
sched_200_100_orig 459 49 404 272
sched_50_50_scaled 29 3 17 9
sched_100_50_scaled 34 7 41 40
sched_100_100_scaled 138 16 73 239
sched_200_100_scaled 372 49 245 409


Table 4: Optimal values, SOCP problems
PROBLEM LOQO MOSEK SDPT3 SeDuMi
nb -.050703 -.050703 -.050679 -.050703
nb_L1 -13.0123 -13.0123 -13.0123 -13.0123
nb_L2 -1.6290 -1.6290 -1.6290 -1.6290
nb_L2_Bessel -.10257 -.10257 -.10257 -.10257
nql30 .94603 .94603 .94605 .94604
nql60 .93505 .93505 .93512 .9351
nql180 - .9277 - -
qssp30 6.4967 6.4967 6.4967 6.4967
qssp60 6.5627 6.5627 6.5627 6.5627
qssp180 - 6.6395 - -
sched_50_50_orig 26673 26673 26671 26673
sched_100_50_orig 181890 181890 181831 181890
sched_100_100_orig 717368 717368 702797 717368
sched_200_100_orig 141360 141360 140863 141360
sched_50_50_scaled 7.85204 7.85204 7.85306 7.85204
sched_100_50_scaled 67.1650 67.1663 67.1736 67.1650
sched_100_100_scaled 27.3308 27.3315 26.9810 27.3308
sched_200_100_scaled 51.8120 51.8125 51.7538 51.8120


Table 5: Error Measures, SOCP problems
PROB/ERROR SDPT3 SeDu.. PROB/ERROR SDPT3 SeDu..
nb/1 .18e-4 .86e-12 nb_L1/1 .69e-4 .83e-12
nb/3 .10e-7 0 nb_L1/3 .40e-8 0
nb/4 0 .14e-14 nb_L1/4 0 .57e-13
nb/5 .21e-3 .53e-15 nb_L1/5 .14e-4 .82e-11
nb/6 .22e-3 .88e-13 nb_L1/6 .14e-4 .77e-11
nb_L2/1 .68e-8 .85e-12 nb_L2_Bessel/1 .77e-8 .39e-13
nb_L2/3 .15e-9 0 nb_L2_Bessel/3 .23e-10 0
nb_L2/4 0 .12e-12 nb_L2_Bessel/4 0 .28e-13
nb_L2/5 .11e-7 .26e-10 nb_L2_Bessel/5 .88e-7 .82e-11
nql30/1 .57e-7 .97e-12 nql60/1 .40e-6 .30e-12
nql30/3 .48e-8 0 nql60/3 .10e-7 0
nql30/4 0 .11e-12 nql60/4 0 .14e-13
nql30/5 .17e-4 -.13e-11 nql60/5 .43e-7 -.67e-13
nql30/6 .37e-4 .57e-13 nql60/6 .10e-4 .70e-14
qssp30/1 .72e-7 .70e-12 qssp60/1 .46e-4 .12e-11
qssp30/3 .11e-8 0 qssp60/3 .22e-8 0
qssp30/4 0 .28e-14 qssp60/4 0 .42e-14
qssp30/5 .71e-6 -.51e-13 qssp60/5 .62e-4 .16e-12
qssp30/6 .76e-6 .47e-14 qssp60/6 .20e-4 .10e-13
sched_50_50_orig/1 .67e-3 .51e-6 sched_50_50_scaled/1 .12e-3 .93e-8
sched_50_50_orig/3 .27e-8 0 sched_50_50_scaled/3 .41e-14 0
sched_50_50_orig/4 0 0 sched_50_50_scaled/4 0 .43e-15
sched_50_50_orig/5 -.87e-4 .13e-11 sched_50_50_scaled/5 .16e-4 -.17e-12
sched_50_50_orig/6 .61e-5 .86e-11 sched_50_50_scaled/6 .30e-4 .13e-12
sched_100_50_orig/1 .62e-3 .94e-5 sched_100_50_scaled/1 .83e-3 .37e-7
sched_100_50_orig/2 0 .57e-10 sched_100_50_scaled/2 0 .68e-13
sched_100_50_orig/3 .31e-10 0 sched_100_50_scaled/3 .90e-12 0
sched_100_50_orig/4 0 .57e-10 sched_100_50_scaled/4 0 .21e-13
sched_100_50_orig/5 -.80e-3 -.11e-9 sched_100_50_scaled/5 .12e-3 .67e-11
sched_100_50_orig/6 .19e-5 -.10e-10 sched_100_50_scaled/6 .11e-3 -.10e-12
sched_100_100_orig/1 .52e-1 .15e1 sched_100_100_scaled/1 .44e-1 .11e-5
sched_100_100_orig/3 .11e-9 0 sched_100_100_scaled/3 .21e-13 0
sched_100_100_orig/4 0 .28e-8 sched_100_100_scaled/4 0 .67e-14
sched_100_100_orig/5 -.19e-1 .19e-10 sched_100_100_scaled/5 -.42e-2 .12e-10
sched_100_100_orig/6 .47e-6 .13e-6 sched_100_100_scaled/6 .14e-1 .47e-11
sched_200_100_orig/1 .61e-1 .34e-4 sched_200_100_scaled/1 .28e-2 .12e-6
sched_200_100_orig/2 0 .36e-10 sched_200_100_scaled/2 0 .15e-12
sched_200_100_orig/3 .32e-8 0 sched_200_100_scaled/3 .58e-8 0
sched_200_100_orig/4 0 .41e-10 sched_200_100_scaled/4 0 .80e-13
sched_200_100_orig/5 -.44e-2 -.78e-10 sched_200_100_scaled/5 -.84e-3 .98e-11
sched_200_100_orig/6 .32e-5 -.82e-10 sched_200_100_scaled/6 .72e-3 -.10e-12


Table 6: CPU times in seconds, small and medium SDP problems; S semidefinite, Q quadratic, L linear; MM: memory exceeded; NA: not applicable
PROB/TYPE BMP BMZ BDL CSD DSD SDA SD3 SeD
toruspm3-8-50/S 6 40 15 99 42 435 80 955
torusg3-8/S 12 47 15 106 43 650 82 1311
bm1/S 53 142 110 fail 1282 6532 749 30661
filter48_socp/SQL NA NA NA 504 fail 2348 53 12
filtinf1/SQL NA NA NA fail fail 2008 fail 12
minphase/S NA NA NA fail 25 2 6 5
truss5/S NA NA NA 4 17 4 7 4
truss8/S NA NA NA 23 222 45 35 27
hinf12/S NA NA NA fail 1 1 5 1
hinf13/S NA NA NA fail 1 1 4 1
copo14/SL NA NA NA 54 1004 226 33 30
copo23/SL NA NA NA 3607 fail 38894 1575 5651
copo68/SL NA NA NA MM MM MM MM MM
hamming_7_5_6/S 4 360 1 89 115 495 52 365
hamming_9_8/S 15 383 1 328 999 fail 183 1482


Table 7: CPU times in seconds, large SDP problems; S semidefinite, L linear; MM: memory exceeded; *: see fourth paragraph in section SDP problems
PROB/TYPE BMPR BMZ BUNDLE CSDP DSDP  
toruspm3-15-50/S 172 4182 462 15857 16450  
torusg3-15/S 144 5043 701 16006 17897  
fap09/SL NA 1424 14972 fail MM  
fap25/SL NA 9.97e5 1.38e6 MM MM  
fap36/SL NA 1.53e7* 7.33e6* MM MM  
biomedP/S 5407 fail 17470 MM MM  
industry2/S 9515 MM 101074 MM MM  
hamming_8_3_4/S 139 3207 16 MM MM  
hamming_9_5_6/S 569 63744 8 MM MM  
hamming_10_2/S 616 7580 116 MM MM  
hamming_11_2/S 1423 57541 243 MM MM  


Table 8: Typical Memory Requirements in MB
PROBLEM BP BZ BD CS DS LO MS SA ST Se
torusg3-8 - - - 31 9.4 - - 82 44 113
torusg3-15 22 44.6 19 1450 205 - - - - -
fap09 - 5 10 - - - - - - -
bm1 4 3.1 8.7 99 21 - - 245 263 271
nql30 - - - 939 - 259 3 - - 43
qssp60 - - - - - 1136 35 - - 295
nb - - - 276 841 43 14 $ >$335 188 47
copo14 - - - 16 26 - - 18 47 48
ham_7_5_6 1.5 1.8 3.4 28 40 - - 31 70 201
ham_9_8 3.6 3.4 5 70 103 - - 118 156 364


Table 9: Optimal values, SDP problems; inf: infeasible
PROB BMP BMZ BDL CSD DSD SDA SD3 SeD
to.3-8-50 527.65 527.85 527.81 527.81 527.82 527.81 527.81 527.81
to.-15-50 3475.1 3475.3 3475.1 3474.8 3474.8 - - -
to.g3-8 457.34 457.38 457.36 457.36 457.36 457.36 457.36 457.36
to.g3-15 3134.6 3134.7 3134.6 3134.6 3134.6 - - -
fap09 - 10.642 10.797 - - - - -
fap25 - 11.682 12.538 - - - - -
fap36 - 63.775 63.767 - - - - -
bm1 23.440 23.425 23.438 - 23.421 23.46 23.440 23.439
biomedP 33.601 - 33.600 - - - - -
industr.2 65.644 - 65.603 - - - - -
filt._socp - - - 1.4161 - 1.4161 1.4161 1.4161
filtinf1 - - - - - inf inf inf
mi.phase - - - - 5.59 5.98 5.98 5.98
truss5 - - - 132.64 132.55 132.64 132.64 132.64
truss8 - - - 133.11 133.00 133.15 133.11 133.11
hinf12 - - - - -.98e-6 -2.98e-1 -7.86e-1 -2.31e-2
hinf13 - - - - -44.34 -47.28 -46.64 -44.38
copo14 - - - -3.5e-9 -7.9e-8 1.e-8 1.e-10 -3.e-11
copo23 - - - -2.e-8 - 8.e-9 -1.e-8 -2.e-10
h._7_5_6 42.663 42.676 42.667 42.667 42.67 42.667 42.667 42.667
h._8_3_4 25.60 25.64 25.60 - - - - -
ha._9_8 224 224.03 224 224 224.01 - 224 224
h._9_5_6 85.334 85.351 256/3 - - - - -
ha._10_2 102.3 102.67 102.4 - - - - -
ha._11_2 170.67 171.86 512/3 - - - - -


Table 10: Error Measures (SDP problems); na: not available; -: does not exist
PROB/ERROR CSDP DSDP SDPA SDPT3 SeDuMi
toruspm3-8-50/1 .45e-13 .24e-11 .50e-13 .24e-10 .12e-11
toruspm3-8-50/3 .77e-15 0 .53e-15 .61e-15 0
toruspm3-8-50/4 0 0 0 0 .14e-12
toruspm3-8-50/5 .29e-7 .30e-3 .19e-7 .22e-8 .86e-15
toruspm3-8-50/6 - - na - -.19e-15
toruspm3-15-50/1 .64e-13 .14e-10 - - -
toruspm3-15-50/3 .20e-14 0 - - -
toruspm3-15-50/4 0 0 - - -
toruspm3-15-50/5 .29e-7 .28e-3 - - -
torusg3-8/1 .48e-13 .29e-11 .17e-8 .22e-10 .10e-11
torusg3-8/3 .87e-15 0 .56e-15 .74e-15 0
torusg3-8/4 0 0 0 0 .77e-12
torusg3-8/5 .35e-7 .30e-3 .43e-7 .33e-9 .17e-13
torusg3-8/6 - - na - .19e-13
torusg3-15/1 .21e-12 .14e-10 - - -
torusg3-15/3 .20e-14 0 - - -
torusg3-15/4 0 0 - - -
torusg3-15/5 .24e-7 .28e-3 - - -
bm1/1 .26e-4 .17e5 .81e-3 .40e-6 .12e-5
bm1/3 .83e-10 0 .30e-12 .82e-11 0
bm1/4 0 .44e-5 0 0 .47e-10
bm1/5 .60e-3 .10e1 .83e-3 .86e-6 .20e-7
bm1/6 .61e-3 .17e-3 na .88e-6 .98e-7


Table 11: Error Measures (SDP problems), continued
PROB/ERROR CSDP DSDP SDPA SDPT3 SeDuMi
filter48_socp/1 - - .35e-6 .12e-5 .80e-7
filter48_socp/3 - - .15e-10 .81e-13 0
filter48_socp/4 - - 0 0 .90e-10
filter48_socp/5 - - .16e-5 .10e-4 .10e-9
filter48_socp/6 - - na .12e-5 .51e-7
hinf12/1 .36e-11 .45e-10 .28e-7 .22e-7 .21e-9
hinf12/3 .35e-6 0 .38e-9 .31e-9 0
hinf12/4 0 0 0 0 0
hinf12/5 -.14e-2 -.96e-6 -.16e0 -.23 -.27e-2
hinf12/6 .46e-3 .90e-7 na .10e-7 .52e-1
hinf13/1 .20e-5 .28e2 .56e-3 .90e-4 .82e-7
hinf13/2 0 .23e-12 0 0 0
hinf13/3 .32e-9 0 .35e-6 .89e-12 0
hinf13/4 0 0 0 0 0
hinf13/5 -.51e-5 .99e-2 -.16e-1 -.18e-1 -.19e-2
hinf13/6 .57e-3 .20e-3 na .29e-4 .47e-1
minphase/1 .68e-7 .16e0 .98e-7 .81e-8 .47e-7
minphase/3 .37e-8 0 0 .57e-12 0
minphase/4 0 0 0 0 0
minphase/5 .25e-4 .14 -.68e-3 -.21e-3 -.74e-4
minphase/6 .63e-4 .15 na .19e-7 ,54e-3
truss5/1 .13e-9 .20e-8 .86e-10 .37e-6 .21e-10
truss5/3 .90e-14 0 .22e-13 .88e-14 0
truss5/4 0 0 0 0 .22e-12
truss5/5 .30e-7 .49e-3 .17e-7 -.25e-9 -.33e-13
truss5/6 - - na .13e-6 .10e-10
truss8/1 .14e-8 .20e-8 .16e-9 .31e-5 .49e-11
truss8/3 .93e-14 0 .46e-8 .92e-14 0
truss8/4 0 0 0 0 .43e-14
truss8/5 .24e-7 .44e-3 .67e-8 -.27e-5 -.14e-14
truss8/6 - - na .12e-6 .17e-11
copo14/1 .11e-13 .25e-8 .63e-10 .10e-9 .73e-11
copo14/3 .42e-14 0 .99e-13 .50e-14 0
copo14/4 0 0 0 0 0
copo14/5 .96e-8 .95e-7 .20e-7 -.13e-8 .14e-10
copo14/6 - .99e-7 na .77e-9 .53e-10
copo23/1 .21e-13 - .21e-9 .15e-8 .29e-10
copo23/3 .96e-14 - .22e-12 .11e-13 0
copo23/4 0 - 0 0 0
copo23/5 .51e-7 - .11e-7 .76e-7 .57e-10
copo23/6 - - na .54e-9 .33e-9
hamming_7_5_6/1 .17e-15 .39e-12 .52e-11 .18e-14 .10e-9
hamming_7_5_6/3 0 0 0 0 0
hamming_7_5_6/4 0 0 0 0 .35e-10
hamming_7_5_6/5 .33e-7 .41e-3 .36e-7 .85e-10 -.33e-9
hamming_7_5_6/6 - - na - .85e-8
hamming_9_8/1 .11e-15 .14e-11 .17e-9 .66e-14 .27e-10
hamming_9_8/2 0 0 .71e-3 0 0
hamming_9_8/3 0 0 0 .81e-13 0
hamming_9_8/4 0 0 0 0 .19e-10
hamming_9_8/5 .62e-8 .49e-13 .10 .37e-8 -.15e-9
hamming_9_8/6 - - na - .12e-7

next up previous
Next: About this document ... Up: paper93 Previous: Bibliography
Hans D. Mittelmann 2002-08-17