70

生成直角Steiner树的程序包

 % ./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: