rsmt500.ps

生成直角Steiner树的程序包

  % @PL 1243 rows, 1791 cols, 26636 nonzeros, 47 slack, 1196 tight.
  % Node 0 LP 14 Solution, length = 160697.580000, 0.02/0.00/0.00/0.00/0.00/0.00/0.10 56
 % 55 fractional variables
 % @LO 3.82 160657.50000000002910383046 0.3526106211
 % @LN 3.82 160697.57999999995809048414 0.3277511071
 % initially 91 congested vertices:
 % find_congested_components found 5 components:
 %	component 0:	3 verts,	3 edges
 %	component 1:	6 verts,	7 edges
 %	component 2:	21 verts,	20 edges
 %	component 3:	16 verts,	22 edges
 %	component 4:	3 verts,	3 edges
 % Enumerating 21 congested vertices.
 % Enumerating 16 congested vertices.
 % @D deleting 47 slack rows
  % @PAP adding 26 rows, 1122 nz to LP
 % @PMEM 3817 rows, 2 blocks, 51148 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1222 rows, 1791 cols, 25234 nonzeros, 31 slack, 1191 tight.
  % @PAP adding 1 rows, 47 nz to LP
  % @PL 1223 rows, 1791 cols, 25281 nonzeros, 32 slack, 1191 tight.
  % @PAP adding 4 rows, 122 nz to LP
  % @PL 1227 rows, 1791 cols, 25403 nonzeros, 23 slack, 1204 tight.
  % Node 0 LP 15 Solution, length = 160745.500000, 0.01/0.00/0.00/0.00/0.00/0.00/0.16 26
 % 20 fractional variables
 % @LO 3.99 160697.57999999995809048414 0.3277511071
 % @LN 3.99 160745.50000000000000000000 0.2980288539
 % Fixed 0 vars to 0 and 1 vars to 1.
 % initially 60 congested vertices:
 % find_congested_components found 3 components:
 %	component 0:	6 verts,	5 edges
 %	component 1:	3 verts,	3 edges
 %	component 2:	3 verts,	3 edges
 % @D deleting 23 slack rows
  % @PAP adding 13 rows, 585 nz to LP
 % @PMEM 3830 rows, 2 blocks, 50550 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1217 rows, 1791 cols, 25130 nonzeros, 26 slack, 1191 tight.
  % @PAP adding 1 rows, 7 nz to LP
  % @PL 1218 rows, 1791 cols, 25137 nonzeros, 32 slack, 1186 tight.
  % Node 0 LP 16 Solution, length = 160752.000000, 0.01/0.00/0.00/0.00/0.00/0.00/0.08 13
 % 33 fractional variables
 % @LO 4.08 160745.50000000000000000000 0.2980288539
 % @LN 4.08 160752.00000000000000000000 0.2939972461
 % initially 25 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	5 verts,	5 edges
 %	component 1:	15 verts,	18 edges
 % Enumerating 15 congested vertices.
 % @D deleting 32 slack rows
  % @PAP adding 9 rows, 332 nz to LP
 % @PMEM 3839 rows, 2 blocks, 50209 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1195 rows, 1791 cols, 23867 nonzeros, 17 slack, 1178 tight.
  % @PAP adding 3 rows, 40 nz to LP
  % @PL 1198 rows, 1791 cols, 23907 nonzeros, 8 slack, 1190 tight.
  % @PAP adding 1 rows, 2 nz to LP
  % @PL 1199 rows, 1791 cols, 23909 nonzeros, 8 slack, 1191 tight.
  % Node 0 LP 17 Solution, length = 160755.750000, 0.00/0.00/0.00/0.00/0.00/0.00/0.10 9
 % 22 fractional variables
 % @LO 4.18 160752.00000000000000000000 0.2939972461
 % @LN 4.18 160755.75000000000000000000 0.2916713185
 % @UO 4.19 161226.00000000000000000000 0.2916713185
 % @UN 4.19 161221.00000000000000000000 0.2885790313
 % initially 13 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	6 verts,	5 edges
 %	component 1:	3 verts,	3 edges
 % @D deleting 8 slack rows
  % @PAP adding 14 rows, 651 nz to LP
 % @PMEM 3853 rows, 2 blocks, 49544 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1205 rows, 1791 cols, 24406 nonzeros, 19 slack, 1186 tight.
  % Node 0 LP 18 Solution, length = 160758.555556, 0.01/0.00/0.00/0.00/0.00/0.00/0.04 14
 % 51 fractional variables
 % @LO 4.23 160755.75000000000000000000 0.2885790313
 % @LN 4.23 160758.55555555553291924298 0.2868388389
 % @UO 4.24 161221.00000000000000000000 0.2868388389
 % @UN 4.24 161022.00000000000000000000 0.1636077334
 % Fixed 20 vars to 0 and 7 vars to 1.
 % initially 63 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	32 verts,	32 edges
 %	component 1:	8 verts,	11 edges
 % Enumerating 32 congested vertices.
 % @D deleting 19 slack rows
  % @PAP adding 35 rows, 2019 nz to LP
 % @PMEM 3888 rows, 2 blocks, 47490 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1221 rows, 1791 cols, 25715 nonzeros, 13 slack, 1208 tight.
  % @PAP adding 6 rows, 50 nz to LP
  % @PL 1227 rows, 1791 cols, 25765 nonzeros, 10 slack, 1217 tight.
  % Node 0 LP 19 Solution, length = 160765.750000, 0.02/0.00/0.00/0.00/0.00/0.00/0.08 35
 % 43 fractional variables
 % @LO 4.33 160758.55555555553291924298 0.1636077334
 % @LN 4.33 160765.74999999997089616954 0.1591397449
 % Fixed 2 vars to 0 and 0 vars to 1.
 % initially 48 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	17 verts,	23 edges
 %	component 1:	5 verts,	6 edges
 % Enumerating 17 congested vertices.
 % @D deleting 10 slack rows
  % @PAP adding 4 rows, 358 nz to LP
 % @PMEM 3892 rows, 2 blocks, 47128 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1221 rows, 1791 cols, 25773 nonzeros, 41 slack, 1180 tight.
  % Node 0 LP 20 Solution, length = 160770.333333, 0.00/0.00/0.00/0.00/0.00/0.00/0.05 4
 % 57 fractional variables
 % @LO 4.38 160765.74999999997089616954 0.1591397449
 % @LN 4.38 160770.33333333348855376244 0.1562933429
 % Fixed 2 vars to 0 and 0 vars to 1.
 % initially 93 congested vertices:
 % find_congested_components found 4 components:
 %	component 0:	6 verts,	8 edges
 %	component 1:	18 verts,	25 edges
 %	component 2:	7 verts,	8 edges
 %	component 3:	3 verts,	4 edges
 % Enumerating 18 congested vertices.
 % @D deleting 41 slack rows
  % @PAP adding 13 rows, 547 nz to LP
 % @PMEM 3905 rows, 2 blocks, 46568 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1193 rows, 1791 cols, 25210 nonzeros, 24 slack, 1169 tight.
  % @PAP adding 5 rows, 572 nz to LP
  % @PL 1198 rows, 1791 cols, 25782 nonzeros, 37 slack, 1161 tight.
  % @PAP adding 2 rows, 7 nz to LP
  % @PL 1200 rows, 1791 cols, 25789 nonzeros, 21 slack, 1179 tight.
  % Node 0 LP 21 Solution, length = 160780.562500, 0.00/0.00/0.00/0.00/0.01/0.00/0.11 13
 % 49 fractional variables
 % @LO 4.50 160770.33333333348855376244 0.1562933429
 % @LN 4.50 160780.56249999962165020406 0.1499406913
 % Fixed 1 vars to 0 and 2 vars to 1.
 % initially 46 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	26 verts,	27 edges
 %	component 1:	3 verts,	3 edges
 % Enumerating 26 congested vertices.
 % @D deleting 21 slack rows
  % @PAP adding 7 rows, 654 nz to LP
 % @PMEM 3912 rows, 2 blocks, 45907 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1186 rows, 1791 cols, 25190 nonzeros, 0 slack, 1186 tight.
  % Node 0 LP 22 Solution, length = 160782.250000, 0.00/0.00/0.00/0.00/0.00/0.01/0.03 7
 % 23 fractional variables
 % @LO 4.54 160780.56249999962165020406 0.1499406913
 % @LN 4.54 160782.25000000000000000000 0.1488926979
 % @UO 4.55 161022.00000000000000000000 0.1488926979
 % @UN 4.55 161017.00000000000000000000 0.1457920592
 % Fixed 2 vars to 0 and 0 vars to 1.
 % initially 42 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	9 verts,	9 edges
  % @PAP adding 47 rows, 5472 nz to LP
 % @PMEM 3959 rows, 2 blocks, 40388 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1233 rows, 1791 cols, 30662 nonzeros, 24 slack, 1209 tight.
  % Node 0 LP 23 Solution, length = 160782.500000, 0.02/0.00/0.00/0.00/0.00/0.00/0.04 47
 % 25 fractional variables
 % @LO 4.60 160782.25000000000000000000 0.1457920592
 % @LN 4.60 160782.50000000000000000000 0.1456367961
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 59 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	3 verts,	4 edges
 %	component 1:	3 verts,	3 edges
 % @D deleting 24 slack rows
  % @PAP adding 2 rows, 34 nz to LP
 % @PMEM 3961 rows, 2 blocks, 40352 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1211 rows, 1791 cols, 28232 nonzeros, 11 slack, 1200 tight.
  % Node 0 LP 24 Solution, length = 160782.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 2
 % 23 fractional variables
 % initially 39 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	5 verts,	6 edges
 %	component 1:	3 verts,	3 edges
 % @D deleting 11 slack rows
  % @PAP adding 2 rows, 34 nz to LP
 % @PMEM 3963 rows, 2 blocks, 40316 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1202 rows, 1791 cols, 27339 nonzeros, 44 slack, 1158 tight.
  % @PAP adding 2 rows, 16 nz to LP
  % @PL 1204 rows, 1791 cols, 27355 nonzeros, 24 slack, 1180 tight.
  % @PAP adding 3 rows, 26 nz to LP
  % @PL 1207 rows, 1791 cols, 27381 nonzeros, 31 slack, 1176 tight.
  % Node 0 LP 25 Solution, length = 160783.611111, 0.00/0.00/0.00/0.00/0.00/0.00/0.10 2
 % 45 fractional variables
 % @LO 4.74 160782.50000000000000000000 0.1456367961
 % @LN 4.74 160783.61111111109494231641 0.1449467379
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 54 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	18 verts,	21 edges
 %	component 1:	7 verts,	9 edges
 % Enumerating 18 congested vertices.
 % @D deleting 31 slack rows
  % @PAP adding 7 rows, 531 nz to LP
 % @PMEM 3970 rows, 2 blocks, 39778 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1183 rows, 1791 cols, 25058 nonzeros, 4 slack, 1179 tight.
  % @PAP adding 2 rows, 13 nz to LP
  % @PL 1185 rows, 1791 cols, 25071 nonzeros, 10 slack, 1175 tight.
  % @PAP adding 1 rows, 7 nz to LP
  % @PL 1186 rows, 1791 cols, 25078 nonzeros, 3 slack, 1183 tight.
  % @PAP adding 1 rows, 3 nz to LP
  % @PL 1187 rows, 1791 cols, 25081 nonzeros, 13 slack, 1174 tight.
  % Node 0 LP 26 Solution, length = 160788.125000, 0.00/0.00/0.00/0.00/0.00/0.00/0.14 7
 % 34 fractional variables
 % @LO 4.88 160783.61111111109494231641 0.1449467379
 % @LN 4.88 160788.12500000000000000000 0.1421433762
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 61 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	12 verts,	15 edges
 %	component 1:	6 verts,	6 edges
 % Enumerating 12 congested vertices.
 % @D deleting 13 slack rows
  % @PAP adding 12 rows, 279 nz to LP
 % @PMEM 3982 rows, 2 blocks, 39487 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1186 rows, 1791 cols, 25136 nonzeros, 7 slack, 1179 tight.
  % @PAP adding 7 rows, 690 nz to LP
  % @PL 1193 rows, 1791 cols, 25826 nonzeros, 9 slack, 1184 tight.
  % Node 0 LP 27 Solution, length = 160789.333333, 0.00/0.00/0.00/0.00/0.00/0.00/0.06 12
 % 32 fractional variables
 % @LO 4.94 160788.12500000000000000000 0.1421433762
 % @LN 4.94 160789.33333333328482694924 0.1413929378
 % initially 66 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	29 verts,	29 edges
 % Enumerating 29 congested vertices.
 % @D deleting 9 slack rows
  % @PAP adding 5 rows, 1205 nz to LP
 % @PMEM 3987 rows, 2 blocks, 38277 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1189 rows, 1791 cols, 26804 nonzeros, 5 slack, 1184 tight.
  % Node 0 LP 28 Solution, length = 160791.833333, 0.01/0.00/0.00/0.00/0.00/0.00/0.04 5
 % 41 fractional variables
 % @LO 4.99 160789.33333333328482694924 0.1413929378
 % @LN 4.99 160791.83333333331393077970 0.1398403067
 % Fixed 0 vars to 0 and 1 vars to 1.
 % initially 81 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	3 verts,	3 edges
 %	component 1:	20 verts,	24 edges
 % Enumerating 20 congested vertices.
 % @D deleting 5 slack rows
  % @PAP adding 4 rows, 462 nz to LP
 % @PMEM 3991 rows, 2 blocks, 37811 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1188 rows, 1791 cols, 26710 nonzeros, 14 slack, 1174 tight.
  % Node 0 LP 29 Solution, length = 160793.000000, 0.00/0.00/0.00/0.01/0.00/0.00/0.03 4
 % 32 fractional variables
 % @LO 5.03 160791.83333333331393077970 0.1398403067
 % @LN 5.03 160793.00000000008731149137 0.1391157455
 % @UO 5.04 161017.00000000000000000000 0.1391157455
 % @UN 5.04 160957.00000000000000000000 0.1018905670
 % Fixed 71 vars to 0 and 2 vars to 1.
 % initially 102 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	3 verts,	3 edges
 %	component 1:	18 verts,	19 edges
 % Enumerating 18 congested vertices.
 % @D deleting 14 slack rows
  % @PAP adding 4 rows, 567 nz to LP
 % @PMEM 3995 rows, 2 blocks, 37240 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1178 rows, 1791 cols, 26785 nonzeros, 1 slack, 1177 tight.
  % @PAP adding 1 rows, 24 nz to LP
  % @PL 1179 rows, 1791 cols, 26809 nonzeros, 16 slack, 1163 tight.
  % @PAP adding 2 rows, 278 nz to LP
  % @PL 1181 rows, 1791 cols, 27087 nonzeros, 17 slack, 1164 tight.
  % Node 0 LP 30 Solution, length = 160793.125000, 0.01/0.00/0.00/0.00/0.00/0.00/0.10 4
 % 55 fractional variables
 % @LO 5.14 160793.00000000008731149137 0.1018905670
 % @LN 5.14 160793.12499999950523488224 0.1018129066
 % Fixed 3 vars to 0 and 0 vars to 1.
 % initially 111 congested vertices:
 % find_congested_components found 3 components:
 %	component 0:	22 verts,	24 edges
 %	component 1:	3 verts,	3 edges
 %	component 2:	21 verts,	23 edges
 % Enumerating 22 congested vertices.
 % Enumerating 21 congested vertices.
 % @D deleting 17 slack rows
  % @PAP adding 9 rows, 904 nz to LP
 % @PMEM 4004 rows, 2 blocks, 36327 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1173 rows, 1791 cols, 26189 nonzeros, 3 slack, 1170 tight.
  % @PAP adding 3 rows, 15 nz to LP
  % @PL 1176 rows, 1791 cols, 26204 nonzeros, 15 slack, 1161 tight.
  % Node 0 LP 31 Solution, length = 160793.750000, 0.01/0.00/0.00/0.00/0.00/0.00/0.07 9
 % 71 fractional variables
 % @LO 5.22 160793.12499999950523488224 0.1018129066
 % @LN 5.22 160793.75000000014551915228 0.1014246041
 % Fixed 4 vars to 0 and 0 vars to 1.
 % initially 135 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	70 verts,	76 edges
 % Enumerating 70 congested vertices.
 % @D deleting 15 slack rows
  % @PAP adding 19 rows, 4326 nz to LP
 % @PMEM 4023 rows, 2 blocks, 31982 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1180 rows, 1791 cols, 28866 nonzeros, 18 slack, 1162 tight.
  % Node 0 LP 32 Solution, length = 160794.588235, 0.00/0.00/0.00/0.00/0.00/0.01/0.05 19
 % 79 fractional variables
 % @LO 5.28 160793.75000000014551915228 0.1014246041
 % @LN 5.28 160794.58823529424262233078 0.1009038220
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 104 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	75 verts,	86 edges
 % Enumerating 75 congested vertices.
 % @D deleting 18 slack rows
  % @PAP adding 14 rows, 4484 nz to LP
 % @PMEM 4037 rows, 2 blocks, 27484 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1176 rows, 1791 cols, 29488 nonzeros, 6 slack, 1170 tight.
  % @PAP adding 2 rows, 47 nz to LP
  % @PL 1178 rows, 1791 cols, 29535 nonzeros, 6 slack, 1172 tight.
  % Node 0 LP 33 Solution, length = 160795.750000, 0.00/0.00/0.00/0.00/0.00/0.01/0.08 14
 % 32 fractional variables
 % @LO 5.37 160794.58823529424262233078 0.1009038220
 % @LN 5.37 160795.74999999994179233909 0.1001820362
 % Fixed 4 vars to 0 and 0 vars to 1.
 % initially 101 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	23 verts,	27 edges
 %	component 1:	3 verts,	3 edges
 % Enumerating 23 congested vertices.
 % @D deleting 6 slack rows
  % @PAP adding 3 rows, 256 nz to LP
 % @PMEM 4040 rows, 2 blocks, 27225 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1175 rows, 1791 cols, 27932 nonzeros, 7 slack, 1168 tight.
  % @PAP adding 1 rows, 7 nz to LP
  % @PL 1176 rows, 1791 cols, 27939 nonzeros, 8 slack, 1168 tight.
  % Node 0 LP 34 Solution, length = 160798.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.08 3
 % 47 fractional variables
 % @LO 5.45 160795.74999999994179233909 0.1001820362
 % @LN 5.45 160798.50000000000000000000 0.0984735053
 % @UO 5.46 160957.00000000000000000000 0.0984735053
 % @UN 5.46 160892.00000000000000000000 0.0581135171
 % Fixed 179 vars to 0 and 10 vars to 1.
 % initially 121 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	50 verts,	54 edges
 % Enumerating 50 congested vertices.
 % @D deleting 8 slack rows
  % @PAP adding 11 rows, 2716 nz to LP
 % @PMEM 4051 rows, 2 blocks, 24498 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1179 rows, 1791 cols, 28753 nonzeros, 4 slack, 1175 tight.
  % Node 0 LP 35 Solution, length = 160798.500000, 0.01/0.00/0.00/0.00/0.00/0.00/0.04 11
 % 30 fractional variables
 % initially 98 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	23 verts,	25 edges
 % Enumerating 23 congested vertices.
 % @D deleting 4 slack rows
  % @PAP adding 4 rows, 1665 nz to LP
 % @PMEM 4055 rows, 2 blocks, 22829 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1179 rows, 1791 cols, 28547 nonzeros, 5 slack, 1174 tight.
  % Node 0 LP 36 Solution, length = 160798.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 4
 % 30 fractional variables
 % initially 97 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	23 verts,	25 edges
 % Enumerating 23 congested vertices.
 % @D deleting 5 slack rows
  % @PAP adding 4 rows, 1649 nz to LP
 % @PMEM 4059 rows, 2 blocks, 21176 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1178 rows, 1791 cols, 28673 nonzeros, 3 slack, 1175 tight.
  % Node 0 LP 37 Solution, length = 160798.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 4
 % 38 fractional variables
 % initially 99 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	33 verts,	37 edges
 % Enumerating 33 congested vertices.
 % @D deleting 3 slack rows
  % @PAP adding 4 rows, 1685 nz to LP
 % @PMEM 4063 rows, 2 blocks, 19487 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1179 rows, 1791 cols, 29148 nonzeros, 4 slack, 1175 tight.
  % Node 0 LP 38 Solution, length = 160798.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 4
 % 30 fractional variables
 % initially 98 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	23 verts,	25 edges
 % Enumerating 23 congested vertices.
 % @D deleting 4 slack rows
  % @PAP adding 4 rows, 1665 nz to LP
 % @PMEM 4067 rows, 2 blocks, 17818 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1179 rows, 1791 cols, 29027 nonzeros, 4 slack, 1175 tight.
  % Node 0 LP 39 Solution, length = 160798.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 4