rsmt70.ps

生成直角Steiner树的程序包

  % @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.03 58685.50000000000000000000 1.6746251152
 % @LN 0.03 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.03 58849.50000000000000000000 1.3998492083
 % @LN 0.03 59188.50000000000000000000 0.8318673033
 % @UO 0.03 59685.00000000000000000000 0.8318673033
 % @UN 0.03 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.00 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.01/0.00/0.00/0.00/0.00 1
 % 14 fractional variables
 % @LO 0.04 59333.50000000000000000000 0.4488179729
 % @LN 0.04 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.04 59385.50000000000000000000 0.3615711146
 % @LN 0.04 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.04 59401.50000000000000000000 0.3347259274
 % @LN 0.04 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.00/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.01 1
 % 10 fractional variables
 % @LO 0.05 59415.50000000000000000000 0.1671847433
 % @LN 0.05 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.05 59417.50000000000000000000 0.1638242460
 % @LN 0.05 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.00 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.05 seconds)
EndPlot

% @0 
% N M Nodes LPs P1CPU P2CPU TotCPU
% @1 70 200 1 17 0.00 0.05 0.05
% 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