rsmt500.ps

生成直角Steiner树的程序包

 % 38 fractional variables
 % initially 100 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	33 verts,	37 edges
 % Enumerating 33 congested vertices.
 % @D deleting 4 slack rows
  % @PAP adding 4 rows, 1701 nz to LP
 % @PMEM 4071 rows, 2 blocks, 16113 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1179 rows, 1791 cols, 29067 nonzeros, 6 slack, 1173 tight.
  % Node 0 LP 40 Solution, length = 160798.825581, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 4
 % 56 fractional variables
 % @LO 5.70 160798.50000000000000000000 0.0581135171
 % @LN 5.70 160798.82558139538741670549 0.0579111569
 % Fixed 2 vars to 0 and 0 vars to 1.
 % initially 114 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	51 verts,	58 edges
 % Enumerating 51 congested vertices.
 % @D deleting 6 slack rows
  % @PAP adding 27 rows, 10452 nz to LP
 % @PMEM 4098 rows, 2 blocks, 5634 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1200 rows, 1791 cols, 37614 nonzeros, 44 slack, 1156 tight.
  % @PAP adding 9 rows, 1452 nz to LP
  % @PL 1209 rows, 1791 cols, 39066 nonzeros, 48 slack, 1161 tight.
  % Node 0 LP 41 Solution, length = 160799.293651, 0.01/0.00/0.00/0.00/0.00/0.01/0.09 27
 % 82 fractional variables
 % @LO 5.81 160798.82558139538741670549 0.0579111569
 % @LN 5.81 160799.29365079404669813812 0.0576202354
 % Fixed 2 vars to 0 and 0 vars to 1.
 % initially 135 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	64 verts,	75 edges
 % Enumerating 64 congested vertices.
 % @D deleting 48 slack rows
  % @PAP adding 1 rows, 26 nz to LP
 % @PMEM 4099 rows, 2 blocks, 5607 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1162 rows, 1791 cols, 25325 nonzeros, 0 slack, 1162 tight.
  % Node 0 LP 42 Solution, length = 160799.880952, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 1
 % 69 fractional variables
 % @LO 5.85 160799.29365079404669813812 0.0576202354
 % @LN 5.85 160799.88095238179084844887 0.0572552070
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 125 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	50 verts,	60 edges
 % Enumerating 50 congested vertices.
  % @PAP adding 17 rows, 5298 nz to LP
 % @PMEM 4116 rows, 2 blocks, 292 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1179 rows, 1791 cols, 30623 nonzeros, 21 slack, 1158 tight.
  % Node 0 LP 43 Solution, length = 160800.000000, 0.00/0.00/0.00/0.00/0.00/0.01/0.04 17
 % 34 fractional variables
 % @LO 5.90 160799.88095238179084844887 0.0572552070
 % @LN 5.90 160800.00000000011641532183 0.0571812147
 % initially 24 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	18 verts,	20 edges
 %	component 1:	3 verts,	3 edges
 % Enumerating 18 congested vertices.
 % @D deleting 21 slack rows
  % @PAP adding 2 rows, 35 nz to LP
 % @PMEM 4118 rows, 2 blocks, 255 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1160 rows, 1791 cols, 30006 nonzeros, 22 slack, 1138 tight.
  % @PAP adding 1 rows, 337 nz to LP
  % @PL 1161 rows, 1791 cols, 30343 nonzeros, 24 slack, 1137 tight.
  % Node 0 LP 44 Solution, length = 160800.166667, 0.01/0.00/0.00/0.00/0.00/0.00/0.07 2
 % 79 fractional variables
 % @LO 5.98 160800.00000000011641532183 0.0571812147
 % @LN 5.98 160800.16666666659875772893 0.0570776256
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 130 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	66 verts,	77 edges
 % Enumerating 66 congested vertices.
 % @D deleting 24 slack rows
 % Entering garbage_collect_pool
 % @PMEM 4118 rows, 2 blocks, 255 nzfree, 42 nzwasted, 132024 nztotal
  % @PAP adding 12 rows, 3590 nz to LP
 % @PMEM 4130 rows, 3 blocks, 62410 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1149 rows, 1791 cols, 28901 nonzeros, 1 slack, 1148 tight.
  % @PAP adding 1 rows, 8 nz to LP
  % @PL 1150 rows, 1791 cols, 28909 nonzeros, 20 slack, 1130 tight.
  % @PAP adding 4 rows, 412 nz to LP
  % @PL 1154 rows, 1791 cols, 29321 nonzeros, 26 slack, 1128 tight.
  % Node 0 LP 45 Solution, length = 160801.317582, 0.00/0.00/0.00/0.00/0.00/0.01/0.11 12
 % 75 fractional variables
 % @LO 6.10 160800.16666666659875772893 0.0570776256
 % @LN 6.10 160801.31758241739589720964 0.0563622912
 % Fixed 8 vars to 0 and 0 vars to 1.
 % initially 85 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	64 verts,	70 edges
 % Enumerating 64 congested vertices.
 % @D deleting 26 slack rows
  % @PAP adding 15 rows, 4731 nz to LP
 % @PMEM 4145 rows, 3 blocks, 57664 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1143 rows, 1791 cols, 29485 nonzeros, 1 slack, 1142 tight.
  % Node 0 LP 46 Solution, length = 160801.500000, 0.01/0.00/0.00/0.00/0.00/0.01/0.04 15
 % 16 fractional variables
 % @LO 6.16 160801.31758241739589720964 0.0563622912
 % @LN 6.16 160801.50000000002910383046 0.0562489123
 % initially 3 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	3 edges
 % @D deleting 1 slack rows
  % @PAP adding 1 rows, 11 nz to LP
 % @PMEM 4146 rows, 3 blocks, 57652 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1143 rows, 1791 cols, 29482 nonzeros, 2 slack, 1141 tight.
  % Node 0 LP 47 Solution, length = 160801.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 1
 % 16 fractional variables
 % initially 49 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	3 edges
 % @D deleting 2 slack rows
  % @PAP adding 1 rows, 180 nz to LP
 % @PMEM 4147 rows, 3 blocks, 57471 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1142 rows, 1791 cols, 29632 nonzeros, 1 slack, 1141 tight.
  % Node 0 LP 48 Solution, length = 160801.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.03 1
 % 12 fractional variables
 % @LO 6.23 160801.50000000002910383046 0.0562489123
 % @LN 6.23 160801.50000000052386894822 0.0562489123
 % @UO 6.24 160892.00000000000000000000 0.0562489123
 % @UN 6.24 160845.00000000000000000000 0.0270446703
 % Fixed 340 vars to 0 and 11 vars to 1.
 % initially 50 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	5 verts,	6 edges
 % @D deleting 1 slack rows
  % @PAP adding 1 rows, 188 nz to LP
 % @PMEM 4148 rows, 3 blocks, 57282 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1142 rows, 1791 cols, 29794 nonzeros, 1 slack, 1141 tight.
  % Node 0 LP 49 Solution, length = 160801.500000, 0.01/0.00/0.00/0.00/0.00/0.00/0.04 1
 % 13 fractional variables
 % initially 50 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	7 verts,	8 edges
 % @D deleting 1 slack rows
  % @PAP adding 1 rows, 184 nz to LP
 % @PMEM 4149 rows, 3 blocks, 57097 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1142 rows, 1791 cols, 29710 nonzeros, 1 slack, 1141 tight.
  % Node 0 LP 50 Solution, length = 160801.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 1
 % 17 fractional variables
 % @UO 6.33 160845.00000000000000000000 0.0270446703
 % @UN 6.33 160844.00000000000000000000 0.0264231181
 % Fixed 10 vars to 0 and 1 vars to 1.
 % initially 51 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	9 verts,	11 edges
 % @D deleting 1 slack rows
  % @PAP adding 1 rows, 192 nz to LP
 % @PMEM 4150 rows, 3 blocks, 56904 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1142 rows, 1791 cols, 29722 nonzeros, 5 slack, 1137 tight.
  % @PAP adding 1 rows, 3 nz to LP
  % @PL 1143 rows, 1791 cols, 29725 nonzeros, 25 slack, 1118 tight.
  % @PAP adding 6 rows, 2843 nz to LP
  % @PL 1149 rows, 1791 cols, 32568 nonzeros, 6 slack, 1143 tight.
  % Node 0 LP 51 Solution, length = 160802.205882, 0.01/0.00/0.00/0.00/0.00/0.00/0.12 1
 % 40 fractional variables
 % @LO 6.45 160801.50000000052386894822 0.0264231181
 % @LN 6.45 160802.20588235283503308892 0.0259842566
 % Fixed 7 vars to 0 and 1 vars to 1.
 % initially 81 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	37 verts,	40 edges
 % Enumerating 37 congested vertices.
 % @D deleting 6 slack rows
  % @PAP adding 13 rows, 3398 nz to LP
 % @PMEM 4163 rows, 3 blocks, 53493 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1156 rows, 1791 cols, 32898 nonzeros, 13 slack, 1143 tight.
  % Node 0 LP 52 Solution, length = 160802.205882, 0.00/0.00/0.00/0.00/0.00/0.01/0.03 13
 % 45 fractional variables
 % @LO 6.49 160802.20588235283503308892 0.0259842566
 % @LN 6.49 160802.20588235286413691938 0.0259842566
 % initially 82 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	41 verts,	45 edges
 % Enumerating 41 congested vertices.
 % @D deleting 13 slack rows
  % @PAP adding 11 rows, 3050 nz to LP
 % @PMEM 4174 rows, 3 blocks, 50432 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1154 rows, 1791 cols, 32710 nonzeros, 11 slack, 1143 tight.
  % Node 0 LP 53 Solution, length = 160802.205882, 0.01/0.00/0.01/0.00/0.00/0.00/0.04 11
 % 45 fractional variables
 % @LO 6.55 160802.20588235286413691938 0.0259842566
 % @LN 6.55 160802.20588235289324074984 0.0259842566
 % initially 82 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	39 verts,	43 edges
 % Enumerating 39 congested vertices.
 % @D deleting 11 slack rows
  % @PAP adding 11 rows, 3094 nz to LP
 % @PMEM 4185 rows, 3 blocks, 47327 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1154 rows, 1791 cols, 32922 nonzeros, 11 slack, 1143 tight.
  % Node 0 LP 54 Solution, length = 160802.205882, 0.01/0.00/0.00/0.00/0.00/0.00/0.04 11
 % 50 fractional variables
 % initially 83 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	43 verts,	48 edges
 % Enumerating 43 congested vertices.
 % @D deleting 11 slack rows
  % @PAP adding 11 rows, 3138 nz to LP
 % @PMEM 4196 rows, 3 blocks, 44178 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1154 rows, 1791 cols, 32974 nonzeros, 26 slack, 1128 tight.
  % @PAP adding 6 rows, 3068 nz to LP
  % @PL 1160 rows, 1791 cols, 36042 nonzeros, 30 slack, 1130 tight.
  % Node 0 LP 55 Solution, length = 160802.218677, 0.01/0.00/0.00/0.00/0.00/0.00/0.07 11
 % 87 fractional variables
 % @LO 6.68 160802.20588235289324074984 0.0259842566
 % @LN 6.68 160802.21867749368539080024 0.0259763016
 % initially 144 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	88 verts,	103 edges
 % Enumerating 88 congested vertices.
 % @D deleting 30 slack rows
  % @PAP adding 27 rows, 9671 nz to LP
 % @PMEM 4223 rows, 3 blocks, 34480 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1157 rows, 1791 cols, 38705 nonzeros, 27 slack, 1130 tight.
  % Node 0 LP 56 Solution, length = 160802.218677, 0.01/0.00/0.00/0.00/0.00/0.02/0.04 27
 % 92 fractional variables
 % @LO 6.75 160802.21867749368539080024 0.0259763016
 % @LN 6.75 160802.21867749409284442663 0.0259763016
 % initially 145 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	89 verts,	105 edges
 % Enumerating 89 congested vertices.
 % @D deleting 27 slack rows
  % @PAP adding 27 rows, 9862 nz to LP
 % @PMEM 4250 rows, 3 blocks, 24591 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1157 rows, 1791 cols, 39165 nonzeros, 2 slack, 1155 tight.
  % Node 0 LP 57 Solution, length = 160802.500000, 0.01/0.00/0.01/0.00/0.00/0.01/0.06 27
 % 11 fractional variables
 % @LO 6.84 160802.21867749409284442663 0.0259763016
 % @LN 6.84 160802.50000000000000000000 0.0258013976
 % Fixed 3 vars to 0 and 0 vars to 1.
 % initially 3 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	4 edges
 % @D deleting 2 slack rows
  % @PAP adding 1 rows, 7 nz to LP
 % @PMEM 4251 rows, 3 blocks, 24583 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1156 rows, 1791 cols, 39163 nonzeros, 1 slack, 1155 tight.
  % Node 0 LP 58 Solution, length = 160802.500000, 0.02/0.00/0.00/0.00/0.00/0.00/0.03 1
 % 7 fractional variables
 % @LO 6.89 160802.50000000000000000000 0.0258013976
 % @LN 6.89 160802.50000000002910383046 0.0258013976
 % initially 10 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	3 edges
 % @D deleting 1 slack rows
  % @PAP adding 1 rows, 23 nz to LP
 % @PMEM 4252 rows, 3 blocks, 24559 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1156 rows, 1791 cols, 39182 nonzeros, 35 slack, 1121 tight.
  % @PAP adding 12 rows, 2073 nz to LP
  % @PL 1168 rows, 1791 cols, 41255 nonzeros, 51 slack, 1117 tight.
  % Node 0 LP 59 Solution, length = 160802.737911, 0.02/0.00/0.00/0.00/0.00/0.00/0.10 1
 % 124 fractional variables
 % @LO 7.01 160802.50000000002910383046 0.0258013976
 % @LN 7.01 160802.73791102494578808546 0.0256534835
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 171 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	121 verts,	140 edges
 % Enumerating 121 congested vertices.
 % @D deleting 51 slack rows
  % @PAP adding 47 rows, 21207 nz to LP
 % @PMEM 4299 rows, 3 blocks, 3305 nzfree, 297 nzwasted, 198036 nztotal
  % @PL 1164 rows, 1791 cols, 46361 nonzeros, 4 slack, 1160 tight.
  % @PAP adding 31 rows, 13636 nz to LP
  % @PL 1195 rows, 1791 cols, 59997 nonzeros, 72 slack, 1123 tight.
  % @PAP adding 11 rows, 1719 nz to LP
  % @PL 1206 rows, 1791 cols, 61716 nonzeros, 79 slack, 1127 tight.
  % Node 0 LP 60 Solution, length = 160802.859281, 0.00/0.00/0.01/0.00/0.00/0.06/0.16 47
 % 139 fractional variables
 % @LO 7.24 160802.73791102494578808546 0.0256534835
 % @LN 7.24 160802.85928120688186027110 0.0255780252
 % initially 176 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	136 verts,	156 edges
 % Enumerating 136 congested vertices.
 % @D deleting 79 slack rows
 % Entering garbage_collect_pool
 % @PMEM 4299 rows, 3 blocks, 3305 nzfree, 297 nzwasted, 198036 nztotal
  % @PAP adding 46 rows, 11076 nz to LP
 % @PMEM 4345 rows, 4 blocks, 57930 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1173 rows, 1791 cols, 39212 nonzeros, 1 slack, 1172 tight.
  % Node 0 LP 61 Solution, length = 160803.000000, 0.01/0.00/0.01/0.00/0.00/0.04/0.04 46
 % 12 fractional variables
 % @LO 7.34 160802.85928120688186027110 0.0255780252
 % @LN 7.34 160802.99999999967985786498 0.0254905374
 % Fixed 1 vars to 0 and 0 vars to 1.
 % initially 3 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	3 verts,	4 edges
 % @D deleting 1 slack rows
  % @PAP adding 1 rows, 7 nz to LP
 % @PMEM 4346 rows, 4 blocks, 57922 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1173 rows, 1791 cols, 39214 nonzeros, 0 slack, 1173 tight.
  % @PAP adding 4 rows, 172 nz to LP
  % @PL 1177 rows, 1791 cols, 39386 nonzeros, 23 slack, 1154 tight.
  % @PAP adding 28 rows, 11246 nz to LP
  % @PL 1205 rows, 1791 cols, 50632 nonzeros, 42 slack, 1163 tight.
  % Node 0 LP 62 Solution, length = 160803.883333, 0.01/0.00/0.00/0.00/0.00/0.00/0.18 1
 % 89 fractional variables
 % @LO 7.53 160802.99999999967985786498 0.0254905374
 % @LN 7.53 160803.88333333289483562112 0.0249413510
 % Fixed 6 vars to 0 and 0 vars to 1.
 % initially 138 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	83 verts,	94 edges
 % Enumerating 83 congested vertices.
 % @D deleting 42 slack rows
  % @PAP adding 15 rows, 6397 nz to LP
 % @PMEM 4361 rows, 4 blocks, 51510 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1178 rows, 1791 cols, 40699 nonzeros, 7 slack, 1171 tight.
  % Node 0 LP 63 Solution, length = 160804.000000, 0.00/0.00/0.00/0.01/0.00/0.01/0.05 15
 % 11 fractional variables
 % @LO 7.60 160803.88333333289483562112 0.0249413510
 % @LN 7.60 160804.00000000011641532183 0.0248688170
 % initially 4 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	4 verts,	5 edges
 % @D deleting 7 slack rows
  % @PAP adding 1 rows, 22 nz to LP
 % @PMEM 4362 rows, 4 blocks, 51487 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1172 rows, 1791 cols, 40584 nonzeros, 13 slack, 1159 tight.
  % @PAP adding 5 rows, 646 nz to LP
  % @PL 1177 rows, 1791 cols, 41230 nonzeros, 24 slack, 1153 tight.
  % Node 0 LP 64 Solution, length = 160804.129787, 0.01/0.00/0.00/0.00/0.00/0.00/0.10 1
 % 99 fractional variables
 % @LO 7.71 160804.00000000011641532183 0.0248688170
 % @LN 7.71 160804.12978723325068131089 0.0247881256
 % Fixed 8 vars to 0 and 0 vars to 1.
 % initially 143 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	90 verts,	104 edges
 % Enumerating 90 congested vertices.
 % @D deleting 24 slack rows
  % @PAP adding 24 rows, 6905 nz to LP
 % @PMEM 4386 rows, 4 blocks, 44558 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1177 rows, 1791 cols, 38529 nonzeros, 27 slack, 1150 tight.
  % Node 0 LP 65 Solution, length = 160804.767241, 0.01/0.00/0.00/0.00/0.00/0.01/0.07 24
 % 97 fractional variables
 % @LO 7.80 160804.12978723325068131089 0.0247881256
 % @LN 7.80 160804.76724137956625781953 0.0243918074
 % Fixed 3 vars to 0 and 0 vars to 1.
 % initially 138 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	87 verts,	101 edges
 % Enumerating 87 congested vertices.
 % @D deleting 27 slack rows
  % @PAP adding 14 rows, 5204 nz to LP
 % @PMEM 4400 rows, 4 blocks, 39340 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1164 rows, 1791 cols, 37129 nonzeros, 2 slack, 1162 tight.
  % @PAP adding 1 rows, 7 nz to LP
  % @PL 1165 rows, 1791 cols, 37136 nonzeros, 13 slack, 1152 tight.
  % @PAP adding 3 rows, 594 nz to LP
  % @PL 1168 rows, 1791 cols, 37730 nonzeros, 16 slack, 1152 tight.
  % @PAP adding 1 rows, 23 nz to LP
  % @PL 1169 rows, 1791 cols, 37753 nonzeros, 22 slack, 1147 tight.
  % Node 0 LP 66 Solution, length = 160805.313793, 0.02/0.00/0.00/0.00/0.00/0.01/0.16 14
 % 114 fractional variables
 % @LO 7.99 160804.76724137956625781953 0.0243918074
 % @LN 7.99 160805.31379310341435484588 0.0240520050
 % Fixed 15 vars to 0 and 1 vars to 1.
 % initially 154 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	107 verts,	123 edges
 % Enumerating 107 congested vertices.
 % @D deleting 22 slack rows
  % @PAP adding 32 rows, 11655 nz to LP
 % @PMEM 4432 rows, 4 blocks, 27653 nzfree, 562 nzwasted, 264048 nztotal
  % @PL 1179 rows, 1791 cols, 42753 nonzeros, 7 slack, 1172 tight.
  % @PAP adding 22 rows, 530