rsmt500.ps

生成直角Steiner树的程序包

 % build_initial_formulation: 0.01 seconds.
% Resuming node 0
  % @PAP adding 501 rows, 7891 nz to LP
  % @PL 501 rows, 1791 cols, 9682 nonzeros, 163 slack, 338 tight.
  % @PAP adding 110 rows, 590 nz to LP
  % @PL 611 rows, 1791 cols, 10272 nonzeros, 197 slack, 414 tight.
  % @PAP adding 103 rows, 678 nz to LP
  % @PL 714 rows, 1791 cols, 10950 nonzeros, 215 slack, 499 tight.
  % @PAP adding 78 rows, 452 nz to LP
  % @PL 792 rows, 1791 cols, 11402 nonzeros, 253 slack, 539 tight.
  % @PAP adding 50 rows, 383 nz to LP
  % @PL 842 rows, 1791 cols, 11785 nonzeros, 253 slack, 589 tight.
  % @PAP adding 36 rows, 194 nz to LP
  % @PL 878 rows, 1791 cols, 11979 nonzeros, 272 slack, 606 tight.
  % @PAP adding 24 rows, 164 nz to LP
  % @PL 902 rows, 1791 cols, 12143 nonzeros, 268 slack, 634 tight.
  % @PAP adding 17 rows, 95 nz to LP
  % @PL 919 rows, 1791 cols, 12238 nonzeros, 270 slack, 649 tight.
  % @PAP adding 12 rows, 103 nz to LP
  % @PL 931 rows, 1791 cols, 12341 nonzeros, 278 slack, 653 tight.
  % @PAP adding 7 rows, 41 nz to LP
  % @PL 938 rows, 1791 cols, 12382 nonzeros, 274 slack, 664 tight.
  % @PAP adding 3 rows, 22 nz to LP
  % @PL 941 rows, 1791 cols, 12404 nonzeros, 275 slack, 666 tight.
  % @PAP adding 5 rows, 44 nz to LP
  % @PL 946 rows, 1791 cols, 12448 nonzeros, 275 slack, 671 tight.
  % @PAP adding 7 rows, 47 nz to LP
  % @PL 953 rows, 1791 cols, 12495 nonzeros, 272 slack, 681 tight.
  % @PAP adding 2 rows, 11 nz to LP
  % @PL 955 rows, 1791 cols, 12506 nonzeros, 272 slack, 683 tight.
  % Node 0 LP 1 Solution, length = 149651.000000, 0.41 0
 % 33 fractional variables
 % @LO 0.43 149651.00000000000000000000 99.9000000000
 % @LN 0.43 149651.00000000000000000000 99.9000000000
 % @UO 0.44 167017.00000000000000000000 10.3977439422
 % @UN 0.44 167017.00000000000000000000 10.3977439422
 % @cutset: 63 connected components.
 % initially 154 congested vertices:
 % find_congested_components found 30 components:
 %	component 0:	4 verts,	4 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
 %	component 6:	3 verts,	3 edges
 %	component 7:	3 verts,	3 edges
 %	component 8:	10 verts,	11 edges
 %	component 9:	5 verts,	5 edges
 %	component 10:	7 verts,	6 edges
 %	component 11:	7 verts,	6 edges
 %	component 12:	7 verts,	5 edges
 %	component 13:	5 verts,	5 edges
 %	component 14:	3 verts,	3 edges
 %	component 15:	3 verts,	3 edges
 %	component 16:	6 verts,	9 edges
 %	component 17:	3 verts,	3 edges
 %	component 18:	7 verts,	6 edges
 %	component 19:	7 verts,	10 edges
 %	component 20:	3 verts,	3 edges
 %	component 21:	3 verts,	3 edges
 %	component 22:	8 verts,	8 edges
 %	component 23:	3 verts,	3 edges
 %	component 24:	3 verts,	3 edges
 %	component 25:	7 verts,	10 edges
 %	component 26:	6 verts,	5 edges
 %	component 27:	5 verts,	6 edges
 %	component 28:	8 verts,	7 edges
 %	component 29:	3 verts,	3 edges
 % @D deleting 272 slack rows
  % @PAP adding 976 rows, 24611 nz to LP
 % @PMEM 2891 rows, 1 blocks, 22748 nzfree, 0 nzwasted, 66012 nztotal
  % @PL 1659 rows, 1791 cols, 33677 nonzeros, 605 slack, 1054 tight.
  % @PAP adding 24 rows, 237 nz to LP
  % @PL 1683 rows, 1791 cols, 33914 nonzeros, 611 slack, 1072 tight.
  % @PAP adding 12 rows, 86 nz to LP
  % @PL 1695 rows, 1791 cols, 34000 nonzeros, 616 slack, 1079 tight.
  % @PAP adding 8 rows, 63 nz to LP
  % @PL 1703 rows, 1791 cols, 34063 nonzeros, 610 slack, 1093 tight.
  % @PAP adding 7 rows, 46 nz to LP
  % @PL 1710 rows, 1791 cols, 34109 nonzeros, 614 slack, 1096 tight.
  % @PAP adding 4 rows, 37 nz to LP
  % @PL 1714 rows, 1791 cols, 34146 nonzeros, 618 slack, 1096 tight.
  % Node 0 LP 2 Solution, length = 158062.875000, 0.01/0.00/0.01/0.00/0.00/0.00/0.90 976
 % 42 fractional variables
 % @LO 1.35 149651.00000000000000000000 10.3977439422
 % @LN 1.35 158062.87500000000000000000 5.3612057455
 % @UO 1.36 167017.00000000000000000000 5.3612057455
 % @UN 1.36 163355.00000000000000000000 3.2396467815
 % @cutset: 22 connected components.
 % initially 116 congested vertices:
 % find_congested_components found 18 components:
 %	component 0:	5 verts,	4 edges
 %	component 1:	3 verts,	3 edges
 %	component 2:	6 verts,	6 edges
 %	component 3:	5 verts,	4 edges
 %	component 4:	3 verts,	3 edges
 %	component 5:	3 verts,	3 edges
 %	component 6:	3 verts,	3 edges
 %	component 7:	7 verts,	8 edges
 %	component 8:	5 verts,	4 edges
 %	component 9:	5 verts,	4 edges
 %	component 10:	7 verts,	6 edges
 %	component 11:	3 verts,	3 edges
 %	component 12:	3 verts,	3 edges
 %	component 13:	3 verts,	3 edges
 %	component 14:	5 verts,	5 edges
 %	component 15:	9 verts,	9 edges
 %	component 16:	3 verts,	3 edges
 %	component 17:	6 verts,	6 edges
 % @D deleting 618 slack rows
  % @PAP adding 255 rows, 6743 nz to LP
 % @PMEM 3146 rows, 1 blocks, 15750 nzfree, 0 nzwasted, 66012 nztotal
  % @PL 1351 rows, 1791 cols, 26491 nonzeros, 218 slack, 1133 tight.
  % @PAP adding 17 rows, 145 nz to LP
  % @PL 1368 rows, 1791 cols, 26636 nonzeros, 224 slack, 1144 tight.
  % @PAP adding 9 rows, 51 nz to LP
  % @PL 1377 rows, 1791 cols, 26687 nonzeros, 255 slack, 1122 tight.
  % @PAP adding 5 rows, 22 nz to LP
  % @PL 1382 rows, 1791 cols, 26709 nonzeros, 253 slack, 1129 tight.
  % @PAP adding 1 rows, 5 nz to LP
  % @PL 1383 rows, 1791 cols, 26714 nonzeros, 253 slack, 1130 tight.
  % Node 0 LP 3 Solution, length = 159560.500000, 0.01/0.00/0.00/0.00/0.00/0.00/0.42 255
 % 60 fractional variables
 % @LO 1.78 158062.87500000000000000000 3.2396467815
 % @LN 1.78 159560.50000000000000000000 2.3228551315
 % @UO 1.79 163355.00000000000000000000 2.3228551315
 % @UN 1.79 163182.00000000000000000000 2.2193011484
 % @cutset: 11 connected components.
 % initially 107 congested vertices:
 % find_congested_components found 13 components:
 %	component 0:	3 verts,	3 edges
 %	component 1:	3 verts,	3 edges
 %	component 2:	4 verts,	5 edges
 %	component 3:	3 verts,	3 edges
 %	component 4:	6 verts,	5 edges
 %	component 5:	5 verts,	7 edges
 %	component 6:	3 verts,	3 edges
 %	component 7:	7 verts,	9 edges
 %	component 8:	4 verts,	5 edges
 %	component 9:	5 verts,	7 edges
 %	component 10:	9 verts,	7 edges
 %	component 11:	3 verts,	3 edges
 %	component 12:	3 verts,	3 edges
 % @D deleting 253 slack rows
  % @PAP adding 190 rows, 7331 nz to LP
 % @PMEM 3336 rows, 1 blocks, 8229 nzfree, 0 nzwasted, 66012 nztotal
  % @PL 1320 rows, 1791 cols, 27756 nonzeros, 115 slack, 1205 tight.
  % @PAP adding 7 rows, 43 nz to LP
  % @PL 1327 rows, 1791 cols, 27799 nonzeros, 112 slack, 1215 tight.
  % @PAP adding 1 rows, 10 nz to LP
  % @PL 1328 rows, 1791 cols, 27809 nonzeros, 112 slack, 1216 tight.
  % @PAP adding 2 rows, 25 nz to LP
  % @PL 1330 rows, 1791 cols, 27834 nonzeros, 111 slack, 1219 tight.
  % @PAP adding 1 rows, 4 nz to LP
  % @PL 1331 rows, 1791 cols, 27838 nonzeros, 112 slack, 1219 tight.
  % Node 0 LP 4 Solution, length = 160038.500000, 0.06/0.00/0.00/0.00/0.00/0.00/0.31 190
 % 45 fractional variables
 % @LO 2.15 159560.50000000000000000000 2.2193011484
 % @LN 2.15 160038.50000000000000000000 1.9263766837
 % @UO 2.16 163182.00000000000000000000 1.9263766837
 % @UN 2.16 162540.00000000000000000000 1.5390057832
 % @cutset: 6 connected components.
 % initially 94 congested vertices:
 % find_congested_components found 5 components:
 %	component 0:	6 verts,	5 edges
 %	component 1:	6 verts,	5 edges
 %	component 2:	3 verts,	3 edges
 %	component 3:	13 verts,	11 edges
 %	component 4:	27 verts,	26 edges
 % Enumerating 13 congested vertices.
 % Enumerating 27 congested vertices.
 % @D deleting 112 slack rows
  % @PAP adding 45 rows, 1677 nz to LP
 % @PMEM 3381 rows, 1 blocks, 6507 nzfree, 0 nzwasted, 66012 nztotal
  % @PL 1264 rows, 1791 cols, 25876 nonzeros, 123 slack, 1141 tight.
  % @PAP adding 8 rows, 73 nz to LP
  % @PL 1272 rows, 1791 cols, 25949 nonzeros, 140 slack, 1132 tight.
  % @PAP adding 5 rows, 50 nz to LP
  % @PL 1277 rows, 1791 cols, 25999 nonzeros, 126 slack, 1151 tight.
  % @PAP adding 6 rows, 83 nz to LP
  % @PL 1283 rows, 1791 cols, 26082 nonzeros, 127 slack, 1156 tight.
  % Node 0 LP 5 Solution, length = 160325.750000, 0.01/0.00/0.00/0.00/0.00/0.00/0.31 45
 % 108 fractional variables
 % @LO 2.47 160038.50000000000000000000 1.5390057832
 % @LN 2.47 160325.75000000000000000000 1.3622800541
 % @cutset: 3 connected components.
 % initially 131 congested vertices:
 % find_congested_components found 9 components:
 %	component 0:	26 verts,	26 edges
 %	component 1:	12 verts,	15 edges
 %	component 2:	3 verts,	3 edges
 %	component 3:	7 verts,	9 edges
 %	component 4:	10 verts,	9 edges
 %	component 5:	3 verts,	4 edges
 %	component 6:	6 verts,	7 edges
 %	component 7:	8 verts,	8 edges
 %	component 8:	3 verts,	3 edges
 % Enumerating 26 congested vertices.
 % Enumerating 12 congested vertices.
 % @D deleting 127 slack rows
 % Entering garbage_collect_pool
 % @PMEM 3381 rows, 1 blocks, 6507 nzfree, 0 nzwasted, 66012 nztotal
  % @PAP adding 189 rows, 8819 nz to LP
 % @PMEM 3570 rows, 2 blocks, 63469 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1345 rows, 1791 cols, 30410 nonzeros, 149 slack, 1196 tight.
  % @PAP adding 4 rows, 41 nz to LP
  % @PL 1349 rows, 1791 cols, 30451 nonzeros, 169 slack, 1180 tight.
  % @PAP adding 1 rows, 12 nz to LP
  % @PL 1350 rows, 1791 cols, 30463 nonzeros, 165 slack, 1185 tight.
  % Node 0 LP 6 Solution, length = 160436.083333, 0.00/0.00/0.00/0.00/0.00/0.00/0.24 189
 % 84 fractional variables
 % @LO 2.71 160325.75000000000000000000 1.3622800541
 % @LN 2.71 160436.08333333337213844061 1.2943993273
 % @UO 2.72 162540.00000000000000000000 1.2943993273
 % @UN 2.72 161930.00000000000000000000 0.9225694230
 % @cutset: 2 connected components.
 % initially 120 congested vertices:
 % find_congested_components found 6 components:
 %	component 0:	20 verts,	23 edges
 %	component 1:	8 verts,	7 edges
 %	component 2:	3 verts,	3 edges
 %	component 3:	29 verts,	35 edges
 %	component 4:	3 verts,	3 edges
 %	component 5:	3 verts,	3 edges
 % Enumerating 20 congested vertices.
 % Enumerating 29 congested vertices.
 % @D deleting 165 slack rows
  % @PAP adding 22 rows, 806 nz to LP
 % @PMEM 3592 rows, 2 blocks, 62641 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1207 rows, 1791 cols, 23688 nonzeros, 22 slack, 1185 tight.
  % @PAP adding 5 rows, 131 nz to LP
  % @PL 1212 rows, 1791 cols, 23819 nonzeros, 29 slack, 1183 tight.
  % @PAP adding 3 rows, 12 nz to LP
  % @PL 1215 rows, 1791 cols, 23831 nonzeros, 34 slack, 1181 tight.
  % Node 0 LP 7 Solution, length = 160504.230769, 0.01/0.00/0.00/0.00/0.00/0.00/0.15 22
 % 92 fractional variables
 % @LO 2.87 160436.08333333337213844061 0.9225694230
 % @LN 2.87 160504.23076923078042455018 0.8804849199
 % initially 92 congested vertices:
 % find_congested_components found 6 components:
 %	component 0:	29 verts,	37 edges
 %	component 1:	3 verts,	4 edges
 %	component 2:	3 verts,	4 edges
 %	component 3:	9 verts,	11 edges
 %	component 4:	12 verts,	11 edges
 %	component 5:	3 verts,	3 edges
 % Enumerating 29 congested vertices.
 % Enumerating 12 congested vertices.
 % @D deleting 34 slack rows
  % @PAP adding 46 rows, 2138 nz to LP
 % @PMEM 3638 rows, 2 blocks, 60457 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1227 rows, 1791 cols, 24960 nonzeros, 53 slack, 1174 tight.
  % @PAP adding 13 rows, 315 nz to LP
  % @PL 1240 rows, 1791 cols, 25275 nonzeros, 59 slack, 1181 tight.
  % @PAP adding 1 rows, 5 nz to LP
  % @PL 1241 rows, 1791 cols, 25280 nonzeros, 60 slack, 1181 tight.
  % @PAP adding 1 rows, 3 nz to LP
  % @PL 1242 rows, 1791 cols, 25283 nonzeros, 60 slack, 1182 tight.
  % Node 0 LP 8 Solution, length = 160593.500000, 0.00/0.00/0.00/0.01/0.00/0.00/0.20 46
 % 81 fractional variables
 % @LO 3.08 160504.23076923078042455018 0.8804849199
 % @LN 3.08 160593.50000000000000000000 0.8253566356
 % @UO 3.09 161930.00000000000000000000 0.8253566356
 % @UN 3.09 161679.00000000000000000000 0.6713920794
 % initially 119 congested vertices:
 % find_congested_components found 5 components:
 %	component 0:	26 verts,	26 edges
 %	component 1:	3 verts,	4 edges
 %	component 2:	19 verts,	22 edges
 %	component 3:	7 verts,	8 edges
 %	component 4:	6 verts,	5 edges
 % Enumerating 26 congested vertices.
 % Enumerating 19 congested vertices.
 % @D deleting 60 slack rows
  % @PAP adding 30 rows, 1759 nz to LP
 % @PMEM 3668 rows, 2 blocks, 58668 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1212 rows, 1791 cols, 24628 nonzeros, 44 slack, 1168 tight.
  % @PAP adding 14 rows, 602 nz to LP
  % @PL 1226 rows, 1791 cols, 25230 nonzeros, 52 slack, 1174 tight.
  % @PAP adding 2 rows, 14 nz to LP
  % @PL 1228 rows, 1791 cols, 25244 nonzeros, 56 slack, 1172 tight.
  % @PAP adding 1 rows, 15 nz to LP
  % @PL 1229 rows, 1791 cols, 25259 nonzeros, 53 slack, 1176 tight.
  % @PAP adding 3 rows, 20 nz to LP
  % @PL 1232 rows, 1791 cols, 25279 nonzeros, 74 slack, 1158 tight.
  % Node 0 LP 9 Solution, length = 160614.750000, 0.01/0.00/0.00/0.00/0.00/0.00/0.20 30
 % 80 fractional variables
 % @LO 3.29 160593.50000000000000000000 0.6713920794
 % @LN 3.29 160614.75000000000000000000 0.6582487522
 % initially 86 congested vertices:
 % find_congested_components found 4 components:
 %	component 0:	19 verts,	21 edges
 %	component 1:	9 verts,	12 edges
 %	component 2:	27 verts,	28 edges
 %	component 3:	4 verts,	5 edges
 % Enumerating 19 congested vertices.
 % Enumerating 27 congested vertices.
 % @D deleting 74 slack rows
  % @PAP adding 61 rows, 3074 nz to LP
 % @PMEM 3729 rows, 2 blocks, 55533 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1219 rows, 1791 cols, 25077 nonzeros, 34 slack, 1185 tight.
  % @PAP adding 2 rows, 12 nz to LP
  % @PL 1221 rows, 1791 cols, 25089 nonzeros, 35 slack, 1186 tight.
  % @PAP adding 7 rows, 215 nz to LP
  % @PL 1228 rows, 1791 cols, 25304 nonzeros, 38 slack, 1190 tight.
  % @PAP adding 1 rows, 2 nz to LP
  % @PL 1229 rows, 1791 cols, 25306 nonzeros, 38 slack, 1191 tight.
  % @PAP adding 1 rows, 2 nz to LP
  % @PL 1230 rows, 1791 cols, 25308 nonzeros, 37 slack, 1193 tight.
  % Node 0 LP 10 Solution, length = 160640.100000, 0.00/0.00/0.01/0.00/0.00/0.00/0.20 61
 % 69 fractional variables
 % @LO 3.50 160614.75000000000000000000 0.6582487522
 % @LN 3.50 160640.09999999991850927472 0.6425695359
 % @UO 3.50 161679.00000000000000000000 0.6425695359
 % @UN 3.50 161404.00000000000000000000 0.4732844291
 % initially 73 congested vertices:
 % find_congested_components found 2 components:
 %	component 0:	19 verts,	21 edges
 %	component 1:	32 verts,	34 edges
 % Enumerating 19 congested vertices.
 % Enumerating 32 congested vertices.
 % @D deleting 37 slack rows
  % @PAP adding 2 rows, 43 nz to LP
 % @PMEM 3731 rows, 2 blocks, 55488 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1195 rows, 1791 cols, 23490 nonzeros, 6 slack, 1189 tight.
  % @PAP adding 7 rows, 577 nz to LP
  % @PL 1202 rows, 1791 cols, 24067 nonzeros, 20 slack, 1182 tight.
  % Node 0 LP 11 Solution, length = 160645.833333, 0.00/0.00/0.00/0.00/0.00/0.00/0.08 2
 % 88 fractional variables
 % @LO 3.58 160640.09999999991850927472 0.4732844291
 % @LN 3.58 160645.83333333337213844061 0.4697322660
 % initially 106 congested vertices:
 % find_congested_components found 1 components:
 %	component 0:	76 verts,	83 edges
 % Enumerating 76 congested vertices.
 % @D deleting 20 slack rows
  % @PAP adding 1 rows, 18 nz to LP
 % @PMEM 3732 rows, 2 blocks, 55469 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1183 rows, 1791 cols, 23259 nonzeros, 2 slack, 1181 tight.
  % Node 0 LP 12 Solution, length = 160646.583333, 0.00/0.00/0.00/0.00/0.00/0.00/0.04 1
 % 79 fractional variables
 % @LO 3.62 160645.83333333337213844061 0.4697322660
 % @LN 3.62 160646.58333333328482694924 0.4692675935
 % initially 77 congested vertices:
 % find_congested_components found 3 components:
 %	component 0:	11 verts,	13 edges
 %	component 1:	12 verts,	13 edges
 %	component 2:	30 verts,	31 edges
 % Enumerating 11 congested vertices.
 % Enumerating 12 congested vertices.
 % Enumerating 30 congested vertices.
 % @D deleting 2 slack rows
  % @PAP adding 3 rows, 72 nz to LP
 % @PMEM 3735 rows, 2 blocks, 55394 nzfree, 42 nzwasted, 132024 nztotal
  % @PL 1184 rows, 1791 cols, 23235 nonzeros, 4 slack, 1180 tight.
  % @PAP adding 14 rows, 847 nz to LP
  % @PL 1198 rows, 1791 cols, 24082 nonzeros, 11 slack, 1187 tight.
  % Node 0 LP 13 Solution, length = 160657.500000, 0.00/0.00/0.00/0.00/0.00/0.00/0.08 3
 % 86 fractional variables
 % @LO 3.70 160646.58333333328482694924 0.4692675935
 % @LN 3.70 160657.50000000002910383046 0.4625040272
 % @UO 3.72 161404.00000000000000000000 0.4625040272
 % @UN 3.72 161226.00000000000000000000 0.3526106211
 % initially 93 congested vertices:
 % find_congested_components found 4 components:
 %	component 0:	30 verts,	33 edges
 %	component 1:	10 verts,	12 edges
 %	component 2:	11 verts,	12 edges
 %	component 3:	5 verts,	6 edges
 % Enumerating 30 congested vertices.
 % Enumerating 11 congested vertices.
 % @D deleting 11 slack rows
  % @PAP adding 56 rows, 3042 nz to LP
 % @PMEM 3791 rows, 2 blocks, 52296 nzfree, 42 nzwasted, 132024 nztotal