www.pudn.com > geosteiner-3.1.zip > 70
% ./bb % Args: % Phase 1: 0.01 seconds %%BeginSetup 0 10000 0 10000 SetAxes 70 DefineTerminals 1857 2738 DT 2894 8773 DT 1463 5183 DT 6905 8268 DT 3221 2457 DT 3473 730 DT 2983 4045 DT 5486 5208 DT 815 6755 DT 1875 934 DT 606 7576 DT 6045 4078 DT 9323 8669 DT 7952 2547 DT 303 8201 DT 6131 4811 DT 7871 9452 DT 854 1630 DT 5468 655 DT 7539 7194 DT 2588 3671 DT 5319 3872 DT 4004 3636 DT 8823 9370 DT 2183 4813 DT 4853 437 DT 8935 5346 DT 8461 2389 DT 2920 9868 DT 4339 473 DT 8222 1895 DT 9336 5659 DT 5826 447 DT 8995 3322 DT 3337 1432 DT 7140 4825 DT 7970 3168 DT 1959 6377 DT 8240 6048 DT 953 5905 DT 5779 7114 DT 7741 883 DT 5927 7473 DT 3088 4641 DT 8609 9286 DT 4558 9381 DT 7577 1956 DT 8888 4529 DT 3717 7332 DT 7074 9300 DT 1880 753 DT 8823 4604 DT 255 6767 DT 3610 8398 DT 9728 2393 DT 2860 8228 DT 2032 5977 DT 9534 3627 DT 8144 172 DT 1896 1532 DT 6615 4909 DT 3587 126 DT 2628 2673 DT 9761 9724 DT 1941 1952 DT 5552 6945 DT 3436 3149 DT 4392 4101 DT 6746 2567 DT 9328 6317 DT %%EndSetup % initialize_constraint_pool: 0.00 seconds. % Constraint pool initialized with: % 1 Total degree rows 200 coeffs. % 70 Cutset rows 628 coeffs. % 0 Incompatibility rows 0 coeffs. % 171 2-terminal SEC rows 749 coeffs. % 231 Total rows in pool 71 in LP % @PMEM 231 rows, 1 blocks, 4523 nzfree, 0 nzwasted, 6308 nztotal % build_initial_formulation: 0.00 seconds. % Resuming node 0 % @PAP adding 71 rows, 828 nz to LP % @PL 71 rows, 200 cols, 1028 nonzeros, 26 slack, 45 tight. % @PAP adding 21 rows, 111 nz to LP % @PL 92 rows, 200 cols, 1139 nonzeros, 29 slack, 63 tight. % @PAP adding 14 rows, 68 nz to LP % @PL 106 rows, 200 cols, 1207 nonzeros, 25 slack, 81 tight. % @PAP adding 10 rows, 69 nz to LP % @PL 116 rows, 200 cols, 1276 nonzeros, 29 slack, 87 tight. % @PAP adding 10 rows, 49 nz to LP % @PL 126 rows, 200 cols, 1325 nonzeros, 34 slack, 92 tight. % @PAP adding 4 rows, 11 nz to LP % @PL 130 rows, 200 cols, 1336 nonzeros, 35 slack, 95 tight. % @PAP adding 2 rows, 9 nz to LP % @PL 132 rows, 200 cols, 1345 nonzeros, 34 slack, 98 tight. % @PAP adding 1 rows, 2 nz to LP % @PL 133 rows, 200 cols, 1347 nonzeros, 34 slack, 99 tight. % @PAP adding 1 rows, 4 nz to LP % @PL 134 rows, 200 cols, 1351 nonzeros, 36 slack, 98 tight. % @PAP adding 1 rows, 3 nz to LP % @PL 135 rows, 200 cols, 1354 nonzeros, 36 slack, 99 tight. % @PAP adding 1 rows, 2 nz to LP % @PL 136 rows, 200 cols, 1356 nonzeros, 35 slack, 101 tight. % Node 0 LP 1 Solution, length = 56199.000000, 0.01 0 % 0 fractional variables % @LO 0.01 56199.00000000000000000000 99.9000000000 % @LN 0.01 56199.00000000000000000000 99.9000000000 % @UO 0.01 60393.00000000000000000000 6.9445134370 % @UN 0.01 60393.00000000000000000000 6.9445134370 % @cutset: 7 connected components. % initially 19 congested vertices: % find_congested_components found 6 components: % component 0: 3 verts, 3 edges % component 1: 3 verts, 3 edges % component 2: 3 verts, 3 edges % component 3: 3 verts, 3 edges % component 4: 3 verts, 3 edges % component 5: 3 verts, 3 edges % @D deleting 35 slack rows % @PAP adding 13 rows, 138 nz to LP % @PMEM 244 rows, 1 blocks, 4372 nzfree, 0 nzwasted, 6308 nztotal % @PL 114 rows, 200 cols, 1130 nonzeros, 14 slack, 100 tight. % @PAP adding 1 rows, 2 nz to LP % @PL 115 rows, 200 cols, 1132 nonzeros, 15 slack, 100 tight. % @PAP adding 2 rows, 14 nz to LP % @PL 117 rows, 200 cols, 1146 nonzeros, 15 slack, 102 tight. % @PAP adding 1 rows, 3 nz to LP % @PL 118 rows, 200 cols, 1149 nonzeros, 16 slack, 102 tight. % Node 0 LP 2 Solution, length = 58685.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 13 % 17 fractional variables % @LO 0.01 56199.00000000000000000000 6.9445134370 % @LN 0.01 58685.50000000000000000000 2.8273144239 % @UO 0.01 60393.00000000000000000000 2.8273144239 % @UN 0.01 59685.00000000000000000000 1.6746251152 % @cutset: 2 connected components. % initially 25 congested vertices: % find_congested_components found 4 components: % component 0: 4 verts, 5 edges % component 1: 3 verts, 3 edges % component 2: 3 verts, 4 edges % component 3: 3 verts, 3 edges % @D deleting 16 slack rows % @PAP adding 5 rows, 67 nz to LP % @PMEM 249 rows, 1 blocks, 4300 nzfree, 0 nzwasted, 6308 nztotal % @PL 107 rows, 200 cols, 1099 nonzeros, 5 slack, 102 tight. % @PAP adding 1 rows, 2 nz to LP % @PL 108 rows, 200 cols, 1101 nonzeros, 3 slack, 105 tight. % @PAP adding 3 rows, 13 nz to LP % @PL 111 rows, 200 cols, 1114 nonzeros, 3 slack, 108 tight. % @PAP adding 1 rows, 2 nz to LP % @PL 112 rows, 200 cols, 1116 nonzeros, 4 slack, 108 tight. % @PAP adding 1 rows, 5 nz to LP % @PL 113 rows, 200 cols, 1121 nonzeros, 5 slack, 108 tight. % @PAP adding 1 rows, 4 nz to LP % @PL 114 rows, 200 cols, 1125 nonzeros, 3 slack, 111 tight. % @PAP adding 1 rows, 5 nz to LP % @PL 115 rows, 200 cols, 1130 nonzeros, 4 slack, 111 tight. % @PAP adding 1 rows, 3 nz to LP % @PL 116 rows, 200 cols, 1133 nonzeros, 4 slack, 112 tight. % Node 0 LP 3 Solution, length = 58849.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.01 5 % 11 fractional variables % @LO 0.02 58685.50000000000000000000 1.6746251152 % @LN 0.02 58849.50000000000000000000 1.3998492083 % Fixed 2 vars to 0 and 0 vars to 1. % initially 6 congested vertices: % find_congested_components found 1 components: % component 0: 5 verts, 6 edges % @D deleting 4 slack rows % @PAP adding 7 rows, 141 nz to LP % @PMEM 256 rows, 1 blocks, 4152 nzfree, 0 nzwasted, 6308 nztotal % @PL 119 rows, 200 cols, 1228 nonzeros, 6 slack, 113 tight. % @PAP adding 1 rows, 10 nz to LP % @PL 120 rows, 200 cols, 1238 nonzeros, 6 slack, 114 tight. % @PAP adding 2 rows, 12 nz to LP % @PL 122 rows, 200 cols, 1250 nonzeros, 7 slack, 115 tight. % Node 0 LP 4 Solution, length = 59188.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 7 % 19 fractional variables % @LO 0.02 58849.50000000000000000000 1.3998492083 % @LN 0.02 59188.50000000000000000000 0.8318673033 % @UO 0.02 59685.00000000000000000000 0.8318673033 % @UN 0.02 59601.00000000000000000000 0.6921024815 % Fixed 9 vars to 0 and 0 vars to 1. % initially 15 congested vertices: % find_congested_components found 3 components: % component 0: 4 verts, 5 edges % component 1: 3 verts, 3 edges % component 2: 3 verts, 4 edges % @D deleting 7 slack rows % @PAP adding 3 rows, 31 nz to LP % @PMEM 259 rows, 1 blocks, 4118 nzfree, 0 nzwasted, 6308 nztotal % @PL 118 rows, 200 cols, 1217 nonzeros, 1 slack, 117 tight. % @PAP adding 1 rows, 7 nz to LP % @PL 119 rows, 200 cols, 1224 nonzeros, 3 slack, 116 tight. % @PAP adding 1 rows, 2 nz to LP % @PL 120 rows, 200 cols, 1226 nonzeros, 2 slack, 118 tight. % Node 0 LP 5 Solution, length = 59243.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.01 3 % 12 fractional variables % @LO 0.03 59188.50000000000000000000 0.6921024815 % @LN 0.03 59243.50000000000000000000 0.5998221506 % Fixed 4 vars to 0 and 2 vars to 1. % initially 12 congested vertices: % find_congested_components found 2 components: % component 0: 3 verts, 3 edges % component 1: 4 verts, 5 edges % @D deleting 2 slack rows % @PAP adding 2 rows, 33 nz to LP % @PMEM 261 rows, 1 blocks, 4083 nzfree, 0 nzwasted, 6308 nztotal % @PL 120 rows, 200 cols, 1241 nonzeros, 2 slack, 118 tight. % @PAP adding 1 rows, 7 nz to LP % @PL 121 rows, 200 cols, 1248 nonzeros, 0 slack, 121 tight. % @PAP adding 1 rows, 5 nz to LP % @PL 122 rows, 200 cols, 1253 nonzeros, 1 slack, 121 tight. % Node 0 LP 6 Solution, length = 59333.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 2 % 7 fractional variables % @LO 0.03 59243.50000000000000000000 0.5998221506 % @LN 0.03 59333.50000000000000000000 0.4488179729 % Fixed 10 vars to 0 and 1 vars to 1. % initially 12 congested vertices: % find_congested_components found 2 components: % component 0: 3 verts, 3 edges % component 1: 8 verts, 8 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 19 nz to LP % @PMEM 262 rows, 1 blocks, 4063 nzfree, 0 nzwasted, 6308 nztotal % @PL 122 rows, 200 cols, 1255 nonzeros, 2 slack, 120 tight. % Node 0 LP 7 Solution, length = 59385.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 14 fractional variables % @LO 0.03 59333.50000000000000000000 0.4488179729 % @LN 0.03 59385.50000000000000000000 0.3615711146 % Fixed 3 vars to 0 and 0 vars to 1. % initially 16 congested vertices: % find_congested_components found 2 components: % component 0: 5 verts, 7 edges % component 1: 7 verts, 7 edges % @D deleting 2 slack rows % @PAP adding 6 rows, 108 nz to LP % @PMEM 268 rows, 1 blocks, 3949 nzfree, 0 nzwasted, 6308 nztotal % @PL 126 rows, 200 cols, 1340 nonzeros, 1 slack, 125 tight. % @PAP adding 2 rows, 9 nz to LP % @PL 128 rows, 200 cols, 1349 nonzeros, 0 slack, 128 tight. % Node 0 LP 8 Solution, length = 59401.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 6 % 4 fractional variables % @LO 0.03 59385.50000000000000000000 0.3615711146 % @LN 0.03 59401.50000000000000000000 0.3347259274 % Fixed 1 vars to 0 and 0 vars to 1. % initially 9 congested vertices: % find_congested_components found 1 components: % component 0: 8 verts, 8 edges % @PAP adding 1 rows, 13 nz to LP % @PMEM 269 rows, 1 blocks, 3935 nzfree, 0 nzwasted, 6308 nztotal % @PL 129 rows, 200 cols, 1362 nonzeros, 1 slack, 128 tight. % Node 0 LP 9 Solution, length = 59403.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 6 fractional variables % @LO 0.03 59401.50000000000000000000 0.3347259274 % @LN 0.03 59403.50000000000000000000 0.3313702790 % @UO 0.04 59601.00000000000000000000 0.3313702790 % @UN 0.04 59515.00000000000000000000 0.1873477275 % Fixed 19 vars to 0 and 1 vars to 1. % initially 10 congested vertices: % find_congested_components found 1 components: % component 0: 9 verts, 9 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 19 nz to LP % @PMEM 270 rows, 1 blocks, 3915 nzfree, 0 nzwasted, 6308 nztotal % @PL 129 rows, 200 cols, 1372 nonzeros, 1 slack, 128 tight. % Node 0 LP 10 Solution, length = 59407.500000, 0.01/0.00/0.00/0.00/0.00/0.00/0.00 1 % 7 fractional variables % @LO 0.04 59403.50000000000000000000 0.1873477275 % @LN 0.04 59407.50000000000000000000 0.1806267328 % initially 11 congested vertices: % find_congested_components found 1 components: % component 0: 10 verts, 10 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 21 nz to LP % @PMEM 271 rows, 1 blocks, 3893 nzfree, 0 nzwasted, 6308 nztotal % @PL 129 rows, 200 cols, 1378 nonzeros, 0 slack, 129 tight. % @PAP adding 1 rows, 6 nz to LP % @PL 130 rows, 200 cols, 1384 nonzeros, 1 slack, 129 tight. % Node 0 LP 11 Solution, length = 59415.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 8 fractional variables % @LO 0.04 59407.50000000000000000000 0.1806267328 % @LN 0.04 59415.50000000000000000000 0.1671847433 % Fixed 3 vars to 0 and 1 vars to 1. % initially 10 congested vertices: % find_congested_components found 1 components: % component 0: 9 verts, 10 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 16 nz to LP % @PMEM 272 rows, 1 blocks, 3876 nzfree, 0 nzwasted, 6308 nztotal % @PL 130 rows, 200 cols, 1393 nonzeros, 1 slack, 129 tight. % Node 0 LP 12 Solution, length = 59417.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 10 fractional variables % @LO 0.04 59415.50000000000000000000 0.1671847433 % @LN 0.04 59417.50000000000000000000 0.1638242460 % Fixed 1 vars to 0 and 0 vars to 1. % initially 11 congested vertices: % find_congested_components found 1 components: % component 0: 10 verts, 11 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 22 nz to LP % @PMEM 273 rows, 1 blocks, 3853 nzfree, 0 nzwasted, 6308 nztotal % @PL 130 rows, 200 cols, 1402 nonzeros, 1 slack, 129 tight. % Node 0 LP 13 Solution, length = 59421.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 11 fractional variables % @LO 0.04 59417.50000000000000000000 0.1638242460 % @LN 0.04 59421.50000000000000000000 0.1571032513 % initially 12 congested vertices: % find_congested_components found 1 components: % component 0: 11 verts, 12 edges % Enumerating 11 congested vertices. % @D deleting 1 slack rows % @PAP adding 1 rows, 24 nz to LP % @PMEM 274 rows, 1 blocks, 3828 nzfree, 0 nzwasted, 6308 nztotal % @PL 130 rows, 200 cols, 1407 nonzeros, 1 slack, 129 tight. % Node 0 LP 14 Solution, length = 59461.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.01 1 % 14 fractional variables % @LO 0.05 59421.50000000000000000000 0.1571032513 % @LN 0.05 59461.00000000000000000000 0.0907334285 % Fixed 17 vars to 0 and 0 vars to 1. % initially 16 congested vertices: % find_congested_components found 2 components: % component 0: 5 verts, 6 edges % component 1: 7 verts, 7 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 23 nz to LP % @PMEM 275 rows, 1 blocks, 3804 nzfree, 0 nzwasted, 6308 nztotal % @PL 130 rows, 200 cols, 1416 nonzeros, 4 slack, 126 tight. % Node 0 LP 15 Solution, length = 59477.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 12 fractional variables % @LO 0.05 59461.00000000000000000000 0.0907334285 % @LN 0.05 59477.50000000000000000000 0.0630093254 % Fixed 3 vars to 0 and 0 vars to 1. % initially 14 congested vertices: % find_congested_components found 2 components: % component 0: 4 verts, 5 edges % component 1: 7 verts, 7 edges % @D deleting 4 slack rows % @PAP adding 1 rows, 19 nz to LP % @PMEM 276 rows, 1 blocks, 3784 nzfree, 0 nzwasted, 6308 nztotal % @PL 127 rows, 200 cols, 1372 nonzeros, 1 slack, 126 tight. % Node 0 LP 16 Solution, length = 59477.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 16 fractional variables % initially 15 congested vertices: % find_congested_components found 2 components: % component 0: 5 verts, 6 edges % component 1: 7 verts, 7 edges % @D deleting 1 slack rows % @PAP adding 1 rows, 27 nz to LP % @PMEM 277 rows, 1 blocks, 3756 nzfree, 0 nzwasted, 6308 nztotal % @PL 127 rows, 200 cols, 1390 nonzeros, 0 slack, 127 tight. % Node 0 LP 17 Solution, length = 59503.000000, 0.00/0.00/0.00/0.00/0.00/0.00/0.00 1 % 0 fractional variables % @UO 0.05 59515.00000000000000000000 0.0630093254 % @UN 0.05 59503.00000000000000000000 0.0428549821 % * 0 0 59503.0000 59503.0000 % @LO 0.05 59477.50000000000000000000 0.0428549821 % @LN 0.05 59503.00000000000000000000 0.0000000000 % Certificate of solution: % @C 1941 2673 % @C 2920 9381 % @C 3587 473 % @C 6131 4909 % @C 1880 934 % @C 1896 1630 % @C 2983 3671 % @C 3436 3636 % @C 4392 3872 % @C 9323 9370 % @C 2983 4641 % @C 8995 2393 % @C 4853 447 % @C 5468 447 % @C 8935 5659 % @C 9328 5659 % @C 1463 5905 % @C 1959 5977 % @C 6905 7473 % @C 8995 3627 % @C 5552 7114 % @C 7871 9370 % @C 8609 9370 % @C 8888 4604 % @C 606 6767 % @C 2894 8398 % @C 7140 4909 % @C 7539 6048 % @C 3221 2673 % @C 7952 2567 % @C 7952 883 % @C 7952 1895 % @C 7952 1956 % @C 7952 2389 %%Page: 1 1 BeginPlot Plot_Terminals % fs1: 0 64 62 0 T 1941 2673 C 1941 2673 64 T S 1941 2673 62 T S % fs4: 1 28 45 1 T 2920 9381 C 2920 9381 28 T S 2920 9381 45 T S % fs9: 5 61 29 5 T 3587 473 C 3587 473 61 T S 3587 473 29 T S % fs23: 7 15 60 7 T 6131 4909 C 6131 4909 15 T S 6131 4909 60 T S % fs25: 9 50 59 9 T 1880 934 S 1880 934 50 T S 1880 934 59 T C % fs36: 17 59 64 17 T 1896 1630 S 1896 1630 59 T S 1896 1630 64 T C % fs42: 20 6 66 22 20 T 2983 3671 S 2983 3671 6 T S 2983 3671 3436 3636 C 3436 3636 66 T S 3436 3636 22 T S % fs45: 22 67 21 22 T 4392 3872 C 4392 3872 67 T S 4392 3872 21 T S % fs46: 23 12 63 23 T 9323 9370 S 9323 9370 12 T S 9323 9370 63 T C % fs47: 24 6 43 24 T 2983 4641 C 2983 4641 6 T S 2983 4641 43 T S % fs50: 27 33 54 27 T 8995 2393 C 8995 2393 33 T S 8995 2393 54 T S % fs52: 29 25 18 32 29 T 4853 447 C 4853 447 25 T S 4853 447 5468 447 S 5468 447 18 T S 5468 447 32 T S % fs63: 38 26 69 31 38 T 8935 5659 C 8935 5659 26 T S 8935 5659 9328 5659 S 9328 5659 69 T S 9328 5659 31 T S % fs65: 39 2 37 56 39 T 1463 5905 S 1463 5905 2 T S 1463 5905 1959 5977 C 1959 5977 37 T S 1959 5977 56 T S % fs72: 42 3 19 42 T 6905 7473 S 6905 7473 3 T S 6905 7473 19 T C % fs81: 47 33 57 47 T 8995 3627 C 8995 3627 33 T S 8995 3627 57 T S % fs83: 48 65 40 48 T 5552 7114 C 5552 7114 65 T S 5552 7114 40 T S % fs87: 49 16 44 23 49 T 7871 9370 C 7871 9370 16 T S 7871 9370 8609 9370 S 8609 9370 44 T S 8609 9370 23 T S % fs88: 51 47 26 51 T 8888 4604 S 8888 4604 47 T S 8888 4604 26 T C % fs90: 52 10 8 52 T 606 6767 S 606 6767 10 T S 606 6767 8 T C % fs96: 55 1 53 55 T 2894 8398 C 2894 8398 1 T S 2894 8398 53 T S % fs103: 60 35 19 38 60 T 7140 4909 S 7140 4909 35 T S 7140 4909 7539 6048 C 7539 6048 19 T S 7539 6048 38 T S % fs107: 62 4 66 62 T 3221 2673 S 3221 2673 4 T S 3221 2673 66 T C % fs111: 68 13 36 68 T 7952 2567 S 7952 2567 13 T S 7952 2567 36 T C % fs126: 58 41 30 46 27 13 7952 883 58 T C 7952 883 41 T S 7952 883 7952 1895 S 7952 1895 30 T S 7952 1895 7952 1956 S 7952 1956 46 T S 7952 1956 7952 2389 S 7952 2389 27 T S 7952 2389 13 T S % fs137: 40 42 40 T 42 T C % fs155: 11 15 11 T 15 T C % fs158: 5 34 34 T 5 T C % fs166: 10 14 14 T 10 T C % fs167: 11 21 21 T 11 T C % fs169: 8 39 8 T 39 T C % fs175: 2 24 2 T 24 T C % fs180: 4 34 4 T 34 T C % fs183: 48 53 53 T 48 T C % fs186: 3 49 3 T 49 T C (Steiner Minimal Tree: 70 points, length = 59503, 0.06 seconds) EndPlot % @0 % N M Nodes LPs P1CPU P2CPU TotCPU % @1 70 200 1 17 0.01 0.05 0.06 % Z RootZ %Gap RootLPs RootCPU RedMST % @2 59503 59503.000000 0.00000 17 0.05 10.0620 % InitPRows InitPNZ InitLPRows InitLPNZ % @3 231 1554 71 1028 % RootPRows RootPNZ RootLPRows RootLPNZ % @4 277 2275 127 1390 % FinalPRows FinalPNZ FinalLPRows FinalLPNZ % @5 277 2275 127 1390 % SMTFSTs SMTAvgFSTSz SMTMaxFSTSz #2FSTs #3FSTs ... #10FSTS #>10FSTs % @6 35 2.971429 6 10 18 6 0 1 0 0 0 0 0