This is the logging information generated by Concorde for the first run that adds domino-parity (DP) cuts to the root LP relaxation. The starting relaxation (sav.4b) was produced with cuts obtained with four short branch-and-cut runs. The DP-cut run was completed on March 19, 2004.

The details reported below give an indication of the methodology employed in the Concorde code.

concorde_dom -s 99 -B -T tiara49 -Z 2 -S ../sav.4b -P ../pul.root -M ../pla85900.mas -m -C 32 -v
Host: tiara49
Current process id: 8913
Using random seed 99
Set initial upperbound to 144702256 (from tour)
Write tour of length 144702256.00 to pla85900.sol
Prob Name: pla85900
Prob ID: 0
Prob Parent ID: -1
Prob Bounds: (142336549.606168, 142383704.000000)
Prob Exact Lowerbound: 142336549.606156
No section f in file.
No section g in file.
No section d in file.
Branch History
Root Node
Done with read_probfile
Loading lp...done in 0.70 seconds
LP has: 93346 rows 169018 columns 869631 nonzeros
Dual opt returned after 0.44 seconds
Initial LP value: 142336549.606168
Setting tolerances: next cuts 471.5439 next round 47.1544
SETTING MAXCHUNKSIZE = 16
Setting tolerances: next cuts 471.5439 next round 47.1544
CCtsp_init_edgegenerator (50)
..................................................................................... 2361673 edges
LP has: 93346 rows 169018 columns 869631 nonzeros
Loading lp...done in 0.69 seconds
LP has: 93346 rows 169018 columns 869631 nonzeros
Found 500 pool cuts (max viol 5.0000) in 0.96 seconds
Add 432 cuts (Total 7621), LP: 142336549.796841 (38.49 seconds)
Found 357 pool cuts (max viol 1.9102) in 0.93 seconds
Add 251 cuts (Total 7694), LP: 142336549.926333 (24.81 seconds)
Found 164 pool cuts (max viol 0.6533) in 0.97 seconds
Add 62 cuts (Total 7716), LP: 142336549.951655 (17.84 seconds)
Found 90 pool cuts (max viol 0.3151) in 0.92 seconds
Add 22 cuts (Total 7728), LP: 142336549.973754 (11.57 seconds)
Found 76 pool cuts (max viol 0.1787) in 0.96 seconds
Add 15 cuts (Total 7734), LP: 142336549.993409 (9.49 seconds)
Found 37 pool cuts (max viol 0.1328) in 0.99 seconds
Add 8 cuts (Total 7742), LP: 142336549.993409 (1.25 seconds)
Found 29 pool cuts (max viol 0.1385) in 0.93 seconds
Add 1 cuts (Total 7743), LP: 142336549.993409 (1.06 seconds)
Found 28 pool cuts (max viol 0.0019) in 0.95 seconds
Add 0 cuts (Total 7743), LP: 142336549.993409 (0.02 seconds)
Found 12 connect cuts in 0.02 seconds
Add 12 cuts (Total 7755), LP: 142336549.993409 (1.46 seconds)
Found 103 segment cuts in 0.11 seconds
Add 44 cuts (Total 7799), LP: 142336549.993409 (3.50 seconds)
Found 56 fast blossoms in 0.07 seconds
Add 56 cuts (Total 7855), LP: 142336549.993409 (3.23 seconds)
Found 53 Groetschel-Holland blossoms in 0.09 seconds
Add 53 cuts (Total 7908), LP: 142336549.993409 (3.25 seconds)
Block Combs
Type 0: 232 cuts 2.0000 max violation 0.63 seconds
Type 1: 136 cuts 1.9995 max violation 0.47 seconds
Type 2: 111 cuts 1.9996 max violation 0.64 seconds
Type 4: 101 cuts 1.6664 max violation 0.70 seconds
Type 5: 0 cuts 0.0000 max violation 1.73 seconds
Olaf 1: 75 cuts 2.0000 max violation 0.77 seconds
Olaf 2: 117 cuts 2.0000 max violation 0.78 seconds
Olaf 3: 46 cuts 1.7008 max violation 0.59 seconds
Olaf 4: 55 cuts 1.6667 max violation 0.66 seconds
Total Time in block_combs: 7.63
Found 873 block combs in 7.63 seconds
Add 543 cuts (Total 8451), LP: 142336549.993409 (22.71 seconds)
Found 5 exact subtours in 0.03 seconds
Add 5 cuts (Total 8456), LP: 142336549.993409 (1.44 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8457), LP: 142336549.993409 (1.27 seconds)
Found 842 exact subtours in 0.84 seconds
Add 475 cuts (Total 8352), LP: 142336557.108929 (90.67 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 8355), LP: 142336557.108929 (1.12 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 8356), LP: 142336557.108929 (2.51 seconds)
Found 604 exact subtours in 0.66 seconds
Add 407 cuts (Total 7107), LP: 142336790.992646 (207.81 seconds)
Found 43 exact subtours in 0.03 seconds
Add 43 cuts (Total 7150), LP: 142336790.992646 (1.43 seconds)
Found 8 exact subtours in 0.03 seconds
Add 8 cuts (Total 7158), LP: 142336790.992646 (1.08 seconds)
Found 6 exact subtours in 0.03 seconds
Add 6 cuts (Total 7164), LP: 142336790.992646 (1.05 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7165), LP: 142336790.992646 (1.01 seconds)
Found 861 exact subtours in 0.53 seconds
Add 503 cuts (Total 7327), LP: 142336819.665922 (86.13 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 7329), LP: 142336819.665922 (1.08 seconds)
Found 487 exact subtours in 0.54 seconds
Add 215 cuts (Total 7434), LP: 142336838.299318 (20.42 seconds)
Found 5 exact subtours in 0.03 seconds
Add 5 cuts (Total 7439), LP: 142336838.299318 (1.06 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7440), LP: 142336838.299318 (1.02 seconds)
Found 294 exact subtours in 0.60 seconds
Add 67 cuts (Total 7507), LP: 142336838.299318 (3.20 seconds)
Found 256 exact subtours in 0.49 seconds
Add 27 cuts (Total 7534), LP: 142336838.299318 (2.47 seconds)
Found 249 exact subtours in 0.45 seconds
Add 26 cuts (Total 7560), LP: 142336838.299318 (2.21 seconds)
Found 247 exact subtours in 0.48 seconds
Add 21 cuts (Total 7581), LP: 142336838.299318 (1.88 seconds)
Found 236 exact subtours in 0.55 seconds
Add 12 cuts (Total 7593), LP: 142336838.299318 (1.91 seconds)
Found 236 exact subtours in 0.46 seconds
Add 12 cuts (Total 7605), LP: 142336838.299318 (1.30 seconds)
Found 241 exact subtours in 0.45 seconds
Add 11 cuts (Total 7616), LP: 142336838.299318 (1.59 seconds)
Found 233 exact subtours in 0.55 seconds
Add 8 cuts (Total 7624), LP: 142336838.299318 (1.29 seconds)
Found 232 exact subtours in 0.52 seconds
Add 8 cuts (Total 7632), LP: 142336838.299318 (1.36 seconds)
Found 233 exact subtours in 0.53 seconds
Add 7 cuts (Total 7639), LP: 142336838.299318 (1.40 seconds)
Found 231 exact subtours in 0.56 seconds
Add 9 cuts (Total 7648), LP: 142336838.299318 (1.41 seconds)
Found 231 exact subtours in 0.54 seconds
Add 9 cuts (Total 7657), LP: 142336838.299318 (1.28 seconds)
Found 227 exact subtours in 0.57 seconds
Add 5 cuts (Total 7662), LP: 142336838.299318 (1.14 seconds)
Found 229 exact subtours in 0.56 seconds
Add 7 cuts (Total 7669), LP: 142336838.299318 (1.24 seconds)
Found 228 exact subtours in 0.56 seconds
Add 6 cuts (Total 7675), LP: 142336838.299318 (1.14 seconds)
Found 226 exact subtours in 0.55 seconds
Add 4 cuts (Total 7611), LP: 142336840.465985 (2.40 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7614), LP: 142336840.465985 (1.07 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7615), LP: 142336840.465985 (1.05 seconds)
Found 227 exact subtours in 0.54 seconds
Add 8 cuts (Total 7623), LP: 142336840.465985 (1.19 seconds)
Found 229 exact subtours in 0.53 seconds
Add 10 cuts (Total 7633), LP: 142336840.465985 (1.24 seconds)
Found 224 exact subtours in 0.52 seconds
Add 5 cuts (Total 7638), LP: 142336840.465985 (1.25 seconds)
Found 221 exact subtours in 0.51 seconds
Add 2 cuts (Total 7640), LP: 142336840.465985 (1.17 seconds)
Found 222 exact subtours in 0.51 seconds
Add 3 cuts (Total 7643), LP: 142336840.465985 (1.16 seconds)
Found 221 exact subtours in 0.52 seconds
Add 2 cuts (Total 7645), LP: 142336840.465985 (1.16 seconds)
Found 223 exact subtours in 0.52 seconds
Add 4 cuts (Total 7649), LP: 142336840.465985 (1.35 seconds)
Found 223 exact subtours in 0.53 seconds
Add 3 cuts (Total 7652), LP: 142336840.465985 (1.12 seconds)
Found 221 exact subtours in 0.49 seconds
Add 2 cuts (Total 7654), LP: 142336840.465985 (0.99 seconds)
Found 220 exact subtours in 0.53 seconds
Add 1 cuts (Total 7655), LP: 142336840.465985 (1.08 seconds)
Found 220 exact subtours in 0.54 seconds
Add 1 cuts (Total 7656), LP: 142336840.465985 (1.02 seconds)
Found 220 exact subtours in 0.52 seconds
Add 1 cuts (Total 7657), LP: 142336840.465985 (1.05 seconds)
Found 220 exact subtours in 0.54 seconds
Add 1 cuts (Total 7658), LP: 142336840.465985 (1.04 seconds)
Found 220 exact subtours in 0.51 seconds
Add 1 cuts (Total 7659), LP: 142336840.465985 (1.02 seconds)
Found 219 exact subtours in 0.53 seconds
Add 0 cuts (Total 7659), LP: 142336840.465985 (0.02 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 7164, Ecount = 11680
Shrunk ecount = 11234, ncount = 6915
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6915 nodes, and 11234 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6915 nodes, and 11234 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 4 trivial dominos
GetDual: graph still has 84 extra paralel edges
GetDual: Not One Eliminated edges: 1
GetDual: Number of loops edges: 3
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 4321 nodes and 22442 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 0
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 16395 dominoes.
Done.
DP Separator: Found 16399 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 966.620000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 1653 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2549 combs) ...
Found 5000 domino cuts in 1170.56 seconds
Add 1520 cuts (Total 7039), LP: 142336870.958781 (141.62 seconds)
Added 1520 shrunk domino cuts
Found 500 tighten_lp cuts (max viol 1.2852) in 20.11 seconds
Add 474 cuts (Total 7001), LP: 142336909.884162 (86.78 seconds)
Found 75 CLOSE tighten_lp cuts (max viol 0.5000) in 1.27 seconds
Add 75 cuts (Total 6906), LP: 142336956.546439 (73.69 seconds)
Found 76 double deckers (max viol 3.9999) in 17.54 seconds
Add 76 cuts (Total 6764), LP: 142336972.571199 (24.04 seconds)
Found 21 CLOSE double deckers (max viol 0.7493) in 2.01 seconds
Add 21 cuts (Total 6634), LP: 142336988.461588 (43.76 seconds)
Found 1211 consecutive ones cuts in 421.66 seconds
Add 655 cuts (Total 6653), LP: 142336992.683272 (52.16 seconds)
localcuts classes(8d)... 5449 nodes 8674 edges
localcuts done in 0.12 seconds
Found 32 localcuts in 0.12 seconds
Add 32 cuts (Total 6630), LP: 142336992.683272 (4.75 seconds)
localcuts classes(9d)... 5296 nodes 8434 edges
localcuts done in 0.16 seconds
Found 27 localcuts in 0.16 seconds
Add 27 cuts (Total 6657), LP: 142336992.683272 (1.91 seconds)
localcuts classes(10d)... 5366 nodes 8535 edges
localcuts done in 0.16 seconds
Found 24 localcuts in 0.16 seconds
Add 24 cuts (Total 6681), LP: 142336992.683272 (2.19 seconds)
localcuts classes(11d)... 5385 nodes 8571 edges
localcuts done in 0.33 seconds
Found 22 localcuts in 0.33 seconds
Add 22 cuts (Total 6703), LP: 142336992.683272 (1.96 seconds)
localcuts classes(12d)... 5429 nodes 8639 edges
localcuts done in 0.21 seconds
Found 21 localcuts in 0.21 seconds
Add 21 cuts (Total 6628), LP: 142336995.512631 (5.00 seconds)
localcuts classes(13d)... 5306 nodes 8415 edges
localcuts done in 0.46 seconds
Found 28 localcuts in 0.46 seconds
Add 28 cuts (Total 6656), LP: 142336995.512631 (1.84 seconds)
localcuts classes(14d)... 5390 nodes 8556 edges
localcuts done in 0.20 seconds
Found 24 localcuts in 0.20 seconds
Add 24 cuts (Total 6680), LP: 142336995.512631 (1.51 seconds)
localcuts classes(15d)... 5430 nodes 8619 edges
localcuts done in 0.26 seconds
Found 17 localcuts in 0.26 seconds
Add 17 cuts (Total 6697), LP: 142336995.512631 (1.39 seconds)
localcuts classes(16d)... 5497 nodes 8720 edges
localcuts done in 0.23 seconds
Found 16 localcuts in 0.23 seconds
Add 16 cuts (Total 6713), LP: 142336995.512631 (1.49 seconds)
localcuts spheres(6d/8d)... 5428 nodes 8620 edges
localcuts done in 0.12 seconds
localcuts spheres(7d/9d)... 5428 nodes 8620 edges
localcuts done in 0.12 seconds
localcuts spheres(8d/10d)... 5428 nodes 8620 edges
localcuts done in 0.09 seconds
localcuts spheres(9d/11d)... 5428 nodes 8620 edges
localcuts done in 0.11 seconds
localcuts spheres(10d/12d)... 5428 nodes 8620 edges
localcuts done in 0.11 seconds
localcuts spheres(11d/13d)... 5428 nodes 8620 edges
localcuts done in 0.12 seconds
localcuts spheres(12d/14d)... 5428 nodes 8620 edges
localcuts done in 0.10 seconds
localcuts spheres(13d/15d)... 5428 nodes 8620 edges
localcuts done in 0.11 seconds
localcuts spheres(14d/16d)... 5428 nodes 8620 edges
localcuts done in 0.10 seconds
CCtsp_generate_edges (277700)
Time for Add edges optimize: 23.07 seconds (23.07 total in 1 calls)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 0.72 seconds (23.79 total in 2 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 31.11 seconds (31.11 total in 1 calls)
(SPARSE) 16 edges added, penalty -0.000000, val 142336992.459257
Time for Sparse edge check: 31.13 seconds (31.13 total in 1 calls)
Write Pool: 189448 cuts
Write Domino Pool: 386 cuts
Time for Cutting inside loop: 2805.02 seconds (2805.02 total in 1 calls)
LP has: 92613 rows 169034 columns 824741 nonzeros
Loading lp...done in 0.70 seconds
LP has: 92613 rows 169034 columns 824741 nonzeros
Found 500 pool cuts (max viol 4.0000) in 0.96 seconds
Add 463 cuts (Total 6825), LP: 142337081.498650 (34.08 seconds)
Found 500 pool cuts (max viol 3.9958) in 0.93 seconds
Add 340 cuts (Total 6874), LP: 142337111.540064 (33.87 seconds)
Found 500 pool cuts (max viol 2.0000) in 0.97 seconds
Add 270 cuts (Total 6928), LP: 142337127.126417 (39.64 seconds)
Found 213 pool cuts (max viol 3.0000) in 1.01 seconds
Add 136 cuts (Total 6852), LP: 142337128.128250 (13.94 seconds)
Found 211 pool cuts (max viol 2.0000) in 0.97 seconds
Add 104 cuts (Total 6865), LP: 142337128.153528 (12.47 seconds)
Found 36 pool cuts (max viol 1.0000) in 0.93 seconds
Add 19 cuts (Total 6884), LP: 142337128.153528 (1.69 seconds)
Found 17 pool cuts (max viol 0.0018) in 0.94 seconds
Add 0 cuts (Total 6884), LP: 142337128.153528 (0.03 seconds)
Found 73 connect cuts in 0.02 seconds
Add 73 cuts (Total 6957), LP: 142337128.153528 (1.43 seconds)
Found 88 segment cuts in 0.12 seconds
Add 43 cuts (Total 6948), LP: 142337131.703604 (10.33 seconds)
Found 60 fast blossoms in 0.09 seconds
Add 60 cuts (Total 7008), LP: 142337131.703604 (2.26 seconds)
Found 66 Groetschel-Holland blossoms in 0.08 seconds
Add 61 cuts (Total 7069), LP: 142337131.703604 (3.42 seconds)
Block Combs
Type 0: 288 cuts 2.0000 max violation 0.56 seconds
Type 1: 210 cuts 1.9999 max violation 0.55 seconds
Type 2: 138 cuts 1.9998 max violation 0.45 seconds
Type 3: 141 cuts 1.9997 max violation 0.38 seconds
Type 4: 116 cuts 1.9995 max violation 0.38 seconds
Type 5: 16 cuts 1.4941 max violation 1.79 seconds
Olaf 1: 159 cuts 1.9999 max violation 0.73 seconds
Olaf 2: 136 cuts 2.0000 max violation 0.83 seconds
Olaf 3: 123 cuts 2.0000 max violation 0.68 seconds
Olaf 4: 121 cuts 2.0000 max violation 0.64 seconds
Total Time in block_combs: 7.62
Found 1448 block combs in 7.62 seconds
Add 777 cuts (Total 6902), LP: 142337162.849460 (62.86 seconds)
Found 49 exact subtours in 0.03 seconds
Add 49 cuts (Total 6951), LP: 142337162.849460 (3.48 seconds)
Add 9 cuts (Total 6960), LP: 142337162.849460 (1.32 seconds)
Found 10 exact subtours in 0.03 seconds
Add 10 cuts (Total 6970), LP: 142337162.849460 (1.37 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 6972), LP: 142337162.849460 (1.33 seconds)
Found 3 exact subtours in 0.02 seconds
Add 3 cuts (Total 6975), LP: 142337162.849460 (1.32 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 6977), LP: 142337162.849460 (1.04 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 6978), LP: 142337162.849460 (1.26 seconds)
Found 1 exact subtours in 0.01 seconds
Add 1 cuts (Total 6979), LP: 142337162.849460 (1.02 seconds)
Found 656 exact subtours in 0.55 seconds
Add 459 cuts (Total 7069), LP: 142337162.889866 (32.25 seconds)
Found 7 exact subtours in 0.03 seconds
Add 7 cuts (Total 7076), LP: 142337162.889866 (1.10 seconds)
Found 3 exact subtours in 0.02 seconds
Add 3 cuts (Total 7079), LP: 142337162.889866 (1.06 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7080), LP: 142337162.889866 (1.05 seconds)
Found 325 exact subtours in 0.56 seconds
Add 171 cuts (Total 7251), LP: 142337162.889866 (5.86 seconds)
Found 230 exact subtours in 0.57 seconds
Add 85 cuts (Total 7336), LP: 142337162.889866 (3.97 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7337), LP: 142337162.889866 (1.07 seconds)
Found 177 exact subtours in 0.42 seconds
Add 42 cuts (Total 7379), LP: 142337162.889866 (2.43 seconds)
Found 146 exact subtours in 0.53 seconds
Add 10 cuts (Total 7389), LP: 142337162.889866 (1.83 seconds)
Found 142 exact subtours in 0.56 seconds
Add 7 cuts (Total 7396), LP: 142337162.889866 (1.15 seconds)
Found 144 exact subtours in 0.57 seconds
Add 9 cuts (Total 7405), LP: 142337162.889866 (1.91 seconds)
Found 143 exact subtours in 0.54 seconds
Add 7 cuts (Total 7412), LP: 142337162.889866 (1.52 seconds)
Found 142 exact subtours in 0.48 seconds
Add 7 cuts (Total 7419), LP: 142337162.889866 (1.30 seconds)
Found 140 exact subtours in 0.55 seconds
Add 4 cuts (Total 7423), LP: 142337162.889866 (1.55 seconds)
Found 146 exact subtours in 0.58 seconds
Add 3 cuts (Total 7426), LP: 142337162.889866 (1.21 seconds)
Found 144 exact subtours in 0.58 seconds
Add 2 cuts (Total 7428), LP: 142337162.889866 (1.16 seconds)
Found 143 exact subtours in 0.55 seconds
Add 0 cuts (Total 7428), LP: 142337162.889866 (0.02 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 5825, Ecount = 9508
Shrunk ecount = 9183, ncount = 5682
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 5682 nodes, and 9183 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 5682 nodes, and 9183 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 6 trivial dominos
GetDual: graph still has 80 extra paralel edges
GetDual: Not One Eliminated edges: 1
GetDual: Number of loops edges: 1
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3503 nodes and 18328 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 1
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 13094 dominoes.
Done.
DP Separator: Found 13100 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 942.660000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 3540 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2400 combs) ...
Found 5000 domino cuts in 1100.78 seconds
Add 1614 cuts (Total 7442), LP: 142337174.387467 (116.63 seconds)
Added 1614 shrunk domino cuts
Found 452 tighten_lp cuts (max viol 1.5000) in 16.05 seconds
Add 307 cuts (Total 7293), LP: 142337185.102287 (138.32 seconds)
Found 58 CLOSE tighten_lp cuts (max viol 0.2770) in 1.87 seconds
Add 58 cuts (Total 7235), LP: 142337207.656382 (40.01 seconds)
Found 109 double deckers (max viol 4.0000) in 17.20 seconds
Add 109 cuts (Total 7273), LP: 142337210.475416 (25.91 seconds)
Found 14 CLOSE double deckers (max viol 0.1042) in 1.34 seconds
Add 14 cuts (Total 7111), LP: 142337218.650992 (6.91 seconds)
Found 766 consecutive ones cuts in 258.38 seconds
Add 520 cuts (Total 6696), LP: 142337221.057225 (36.24 seconds)
localcuts spheres(6d/8d)... 4994 nodes 7962 edges
localcuts done in 0.10 seconds
Found 2 localcuts in 0.10 seconds
Add 2 cuts (Total 6698), LP: 142337221.057225 (1.08 seconds)
localcuts spheres(7d/9d)... 4986 nodes 7950 edges
localcuts done in 0.13 seconds
Found 2 localcuts in 0.13 seconds
Add 2 cuts (Total 6700), LP: 142337221.057225 (1.17 seconds)
localcuts spheres(8d/10d)... 4992 nodes 7959 edges
localcuts done in 0.11 seconds
Found 4 localcuts in 0.11 seconds
Add 4 cuts (Total 6704), LP: 142337221.057225 (1.40 seconds)
localcuts spheres(9d/11d)... 4991 nodes 7960 edges
localcuts done in 0.12 seconds
Found 2 localcuts in 0.12 seconds
Add 2 cuts (Total 6706), LP: 142337221.057225 (1.70 seconds)
localcuts spheres(10d/12d)... 5000 nodes 7974 edges
localcuts done in 0.13 seconds
Found 8 localcuts in 0.13 seconds
Add 8 cuts (Total 6714), LP: 142337221.057225 (2.69 seconds)
localcuts spheres(11d/13d)... 5007 nodes 7990 edges
localcuts done in 0.13 seconds
Found 7 localcuts in 0.13 seconds
Add 7 cuts (Total 6721), LP: 142337221.057225 (3.04 seconds)
localcuts spheres(12d/14d)... 5018 nodes 8006 edges
localcuts done in 0.15 seconds
Found 9 localcuts in 0.15 seconds
Add 9 cuts (Total 6730), LP: 142337221.057225 (2.26 seconds)
localcuts spheres(13d/15d)... 5013 nodes 8000 edges
localcuts done in 0.14 seconds
Found 6 localcuts in 0.14 seconds
Add 6 cuts (Total 6736), LP: 142337221.057225 (3.73 seconds)
localcuts spheres(14d/16d)... 5010 nodes 7993 edges
localcuts done in 0.13 seconds
Found 8 localcuts in 0.13 seconds
Add 8 cuts (Total 6744), LP: 142337221.057225 (1.19 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 2.08 seconds (25.87 total in 3 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 7.01 seconds (38.12 total in 2 calls)
(SPARSE) 5 edges added, penalty -0.000000, val 142337219.582186
Time for Sparse edge check: 7.03 seconds (38.16 total in 2 calls)
Write Pool: 190223 cuts
Write Domino Pool: 716 cuts
Time for Cutting inside loop: 2160.78 seconds (4965.80 total in 2 calls)
LP has: 92644 rows 169039 columns 860548 nonzeros
Loading lp...done in 0.72 seconds
LP has: 92644 rows 169039 columns 860535 nonzeros
Found 500 pool cuts (max viol 4.0000) in 0.95 seconds
Add 439 cuts (Total 6804), LP: 142337220.458630 (15.62 seconds)
Found 478 pool cuts (max viol 2.0000) in 0.97 seconds
Add 290 cuts (Total 6788), LP: 142337225.203774 (39.71 seconds)
Found 451 pool cuts (max viol 2.9995) in 0.95 seconds
Add 251 cuts (Total 6832), LP: 142337225.786299 (22.06 seconds)
Found 135 pool cuts (max viol 2.6667) in 0.96 seconds
Add 58 cuts (Total 6810), LP: 142337225.805927 (10.06 seconds)
Found 136 pool cuts (max viol 1.8057) in 0.96 seconds
Add 70 cuts (Total 6880), LP: 142337225.805927 (1.89 seconds)
Found 82 pool cuts (max viol 0.6667) in 0.94 seconds
Add 23 cuts (Total 6903), LP: 142337225.805927 (1.27 seconds)
Found 75 pool cuts (max viol 0.2222) in 0.97 seconds
Add 16 cuts (Total 6919), LP: 142337225.805927 (1.28 seconds)
Found 64 pool cuts (max viol 0.0439) in 0.95 seconds
Add 5 cuts (Total 6924), LP: 142337225.805927 (1.20 seconds)
Found 59 pool cuts (max viol 0.0019) in 0.96 seconds
Add 0 cuts (Total 6924), LP: 142337225.805927 (0.02 seconds)
Found 67 connect cuts in 0.02 seconds
Add 67 cuts (Total 6991), LP: 142337225.805927 (1.26 seconds)
Found 85 segment cuts in 0.13 seconds
Add 36 cuts (Total 6920), LP: 142337225.818029 (4.61 seconds)
Found 58 fast blossoms in 0.07 seconds
Add 58 cuts (Total 6978), LP: 142337225.818029 (1.61 seconds)
Found 55 Groetschel-Holland blossoms in 0.08 seconds
Add 54 cuts (Total 7032), LP: 142337225.818029 (2.10 seconds)
Block Combs
Type 0: 262 cuts 2.0000 max violation 0.62 seconds
Type 1: 211 cuts 2.0000 max violation 0.63 seconds
Type 2: 196 cuts 2.9999 max violation 0.56 seconds
Type 3: 146 cuts 2.9999 max violation 0.50 seconds
Type 4: 87 cuts 1.8480 max violation 0.41 seconds
Type 5: 30 cuts 1.2838 max violation 2.08 seconds
Olaf 1: 160 cuts 2.0000 max violation 0.82 seconds
Olaf 2: 132 cuts 1.9999 max violation 0.91 seconds
Olaf 3: 100 cuts 2.4993 max violation 0.70 seconds
Olaf 4: 119 cuts 1.9998 max violation 0.65 seconds
Total Time in block_combs: 8.49
Found 1443 block combs in 8.49 seconds
Add 755 cuts (Total 7028), LP: 142337231.652183 (69.90 seconds)
Found 23 exact subtours in 0.02 seconds
Add 23 cuts (Total 7051), LP: 142337231.652183 (4.00 seconds)
Add 23 cuts (Total 7074), LP: 142337231.652183 (2.10 seconds)
Found 4 exact subtours in 0.01 seconds
Add 4 cuts (Total 7078), LP: 142337231.652183 (1.52 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7079), LP: 142337231.652183 (1.06 seconds)
Found 645 exact subtours in 0.65 seconds
Add 438 cuts (Total 7095), LP: 142337231.913446 (33.05 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7098), LP: 142337231.913446 (1.08 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7099), LP: 142337231.913446 (1.07 seconds)
Found 408 exact subtours in 0.49 seconds
Add 265 cuts (Total 7364), LP: 142337231.913446 (10.85 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7367), LP: 142337231.913446 (1.21 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7368), LP: 142337231.913446 (1.05 seconds)
Found 246 exact subtours in 0.47 seconds
Add 100 cuts (Total 7468), LP: 142337231.913446 (4.11 seconds)
Found 164 exact subtours in 0.42 seconds
Add 28 cuts (Total 7496), LP: 142337231.913446 (2.11 seconds)
Found 148 exact subtours in 0.46 seconds
Add 11 cuts (Total 7507), LP: 142337231.913446 (2.14 seconds)
Found 146 exact subtours in 0.48 seconds
Add 9 cuts (Total 7516), LP: 142337231.913446 (1.49 seconds)
Found 146 exact subtours in 0.49 seconds
Add 9 cuts (Total 7525), LP: 142337231.913446 (1.37 seconds)
Found 144 exact subtours in 0.43 seconds
Add 8 cuts (Total 7533), LP: 142337231.913446 (1.19 seconds)
Found 141 exact subtours in 0.49 seconds
Add 4 cuts (Total 7537), LP: 142337231.913446 (1.63 seconds)
Found 145 exact subtours in 0.47 seconds
Add 8 cuts (Total 7545), LP: 142337231.913446 (1.28 seconds)
Found 141 exact subtours in 0.46 seconds
Add 4 cuts (Total 7549), LP: 142337231.913446 (1.18 seconds)
Found 138 exact subtours in 0.40 seconds
Add 2 cuts (Total 7551), LP: 142337231.913446 (1.17 seconds)
Found 139 exact subtours in 0.41 seconds
Add 3 cuts (Total 7554), LP: 142337231.913446 (1.11 seconds)
Found 139 exact subtours in 0.42 seconds
Add 3 cuts (Total 7557), LP: 142337231.913446 (1.30 seconds)
Found 138 exact subtours in 0.36 seconds
Add 2 cuts (Total 7559), LP: 142337231.913446 (1.16 seconds)
Found 138 exact subtours in 0.46 seconds
Add 2 cuts (Total 7561), LP: 142337231.913446 (1.14 seconds)
Found 137 exact subtours in 0.43 seconds
Add 1 cuts (Total 7562), LP: 142337231.913446 (1.08 seconds)
Found 137 exact subtours in 0.43 seconds
Add 1 cuts (Total 7563), LP: 142337231.913446 (1.12 seconds)
Found 137 exact subtours in 0.45 seconds
Add 1 cuts (Total 7564), LP: 142337231.913446 (1.15 seconds)
Found 137 exact subtours in 0.42 seconds
Add 1 cuts (Total 7565), LP: 142337231.913446 (1.11 seconds)
Found 136 exact subtours in 0.44 seconds
Add 0 cuts (Total 7565), LP: 142337231.913446 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 6084, Ecount = 9982
Shrunk ecount = 9612, ncount = 5921
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 5921 nodes, and 9612 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 5921 nodes, and 9612 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 5 trivial dominos
GetDual: graph still has 72 extra paralel edges
GetDual: Not One Eliminated edges: 2
GetDual: Number of loops edges: 3
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3693 nodes and 19194 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 2
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 13891 dominoes.
Done.
DP Separator: Found 13896 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 972.500000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2186 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2767 combs) ...
Found 5000 domino cuts in 1133.44 seconds
Add 2071 cuts (Total 7188), LP: 142337386.162468 (431.57 seconds)
Added 2071 shrunk domino cuts
Found 500 tighten_lp cuts (max viol 1.5033) in 19.52 seconds
Add 404 cuts (Total 6837), LP: 142337507.570037 (160.72 seconds)
Found 61 CLOSE tighten_lp cuts (max viol 0.7503) in 1.81 seconds
Add 61 cuts (Total 6776), LP: 142337532.612539 (44.73 seconds)
Found 96 double deckers (max viol 3.6750) in 17.47 seconds
Add 96 cuts (Total 6752), LP: 142337542.774628 (20.49 seconds)
Found 18 CLOSE double deckers (max viol 2.0000) in 1.31 seconds
Add 18 cuts (Total 6690), LP: 142337544.858995 (4.70 seconds)
Found 891 consecutive ones cuts in 460.98 seconds
Add 546 cuts (Total 6716), LP: 142337553.645223 (39.24 seconds)
localcuts spheres(6d/8d)... 5384 nodes 8576 edges
localcuts done in 0.12 seconds
Found 5 localcuts in 0.12 seconds
Add 5 cuts (Total 6721), LP: 142337553.645223 (1.40 seconds)
localcuts spheres(7d/9d)... 5394 nodes 8591 edges
localcuts done in 0.11 seconds
Found 3 localcuts in 0.11 seconds
Add 3 cuts (Total 6724), LP: 142337553.645223 (1.08 seconds)
localcuts spheres(8d/10d)... 5394 nodes 8591 edges
localcuts done in 0.15 seconds
Found 1 localcuts in 0.15 seconds
Add 1 cuts (Total 6725), LP: 142337553.645223 (1.32 seconds)
localcuts spheres(9d/11d)... 5394 nodes 8591 edges
localcuts done in 0.11 seconds
Found 3 localcuts in 0.11 seconds
Add 3 cuts (Total 6728), LP: 142337553.645223 (1.29 seconds)
localcuts spheres(10d/12d)... 5400 nodes 8600 edges
localcuts done in 0.10 seconds
Found 1 localcuts in 0.10 seconds
Add 1 cuts (Total 6729), LP: 142337553.645223 (1.27 seconds)
localcuts spheres(11d/13d)... 5401 nodes 8605 edges
localcuts done in 0.10 seconds
localcuts spheres(12d/14d)... 5401 nodes 8605 edges
localcuts done in 0.10 seconds
Found 1 localcuts in 0.10 seconds
Add 1 cuts (Total 6730), LP: 142337553.645223 (1.88 seconds)
localcuts spheres(13d/15d)... 5412 nodes 8618 edges
localcuts done in 0.11 seconds
localcuts spheres(14d/16d)... 5412 nodes 8618 edges
localcuts done in 0.11 seconds
CCtsp_generate_edges (277700)
Time for Add edges optimize: 58.60 seconds (84.47 total in 4 calls)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.51 seconds (85.98 total in 5 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 67.81 seconds (105.93 total in 3 calls)
(SPARSE) 26 edges added, penalty -0.000000, val 142337344.795595
Time for Sparse edge check: 67.82 seconds (105.98 total in 3 calls)
Write Pool: 190893 cuts
Write Domino Pool: 1271 cuts
Time for Cutting inside loop: 2756.14 seconds (7721.94 total in 3 calls)
LP has: 92630 rows 169065 columns 860802 nonzeros
Loading lp...done in 0.77 seconds
LP has: 92630 rows 169065 columns 860766 nonzeros
Found 500 pool cuts (max viol 3.9995) in 0.96 seconds
Add 321 cuts (Total 7051), LP: 142337344.795595 (11.09 seconds)
Found 500 pool cuts (max viol 1.9913) in 0.96 seconds
Add 459 cuts (Total 6952), LP: 142337347.214590 (68.31 seconds)
Found 500 pool cuts (max viol 1.9671) in 0.96 seconds
Add 253 cuts (Total 6949), LP: 142337347.465323 (29.85 seconds)
Found 156 pool cuts (max viol 1.6792) in 0.96 seconds
Add 86 cuts (Total 6920), LP: 142337347.507421 (10.47 seconds)
Found 118 pool cuts (max viol 1.3416) in 0.94 seconds
Add 50 cuts (Total 6933), LP: 142337347.507866 (3.76 seconds)
Found 98 pool cuts (max viol 0.9989) in 0.98 seconds
Add 35 cuts (Total 6902), LP: 142337347.518886 (7.04 seconds)
Found 90 pool cuts (max viol 2.0000) in 0.94 seconds
Add 31 cuts (Total 6902), LP: 142337347.530552 (5.94 seconds)
Found 98 pool cuts (max viol 1.0000) in 0.97 seconds
Add 47 cuts (Total 6777), LP: 142337347.559574 (10.50 seconds)
Found 168 pool cuts (max viol 2.6667) in 0.94 seconds
Add 115 cuts (Total 6734), LP: 142337347.575051 (7.41 seconds)
Found 72 pool cuts (max viol 0.7777) in 0.96 seconds
Add 28 cuts (Total 6762), LP: 142337347.575051 (1.25 seconds)
Found 50 pool cuts (max viol 0.2500) in 1.01 seconds
Add 6 cuts (Total 6768), LP: 142337347.575051 (1.11 seconds)
Found 46 pool cuts (max viol 0.3333) in 0.97 seconds
Add 2 cuts (Total 6770), LP: 142337347.575051 (0.98 seconds)
Found 44 pool cuts (max viol 0.0019) in 1.02 seconds
Add 0 cuts (Total 6770), LP: 142337347.575051 (0.01 seconds)
Found 72 connect cuts in 0.03 seconds
Add 72 cuts (Total 6842), LP: 142337347.575051 (1.57 seconds)
Found 103 segment cuts in 0.12 seconds
Add 42 cuts (Total 6629), LP: 142337347.870021 (5.38 seconds)
Found 60 fast blossoms in 0.09 seconds
Add 60 cuts (Total 6689), LP: 142337347.870021 (1.19 seconds)
Found 65 Groetschel-Holland blossoms in 0.08 seconds
Add 62 cuts (Total 6751), LP: 142337347.870021 (1.87 seconds)
Block Combs
Type 0: 317 cuts 2.0000 max violation 0.52 seconds
Type 1: 237 cuts 2.0000 max violation 0.63 seconds
Type 2: 158 cuts 2.0000 max violation 0.59 seconds
Type 4: 123 cuts 2.9950 max violation 0.41 seconds
Type 5: 11 cuts 2.3330 max violation 1.46 seconds
Olaf 1: 161 cuts 2.0000 max violation 0.78 seconds
Olaf 2: 148 cuts 2.0000 max violation 0.94 seconds
Olaf 3: 109 cuts 2.9999 max violation 0.81 seconds
Olaf 4: 113 cuts 2.0000 max violation 0.89 seconds
Total Time in block_combs: 7.69
Found 1377 block combs in 7.69 seconds
Add 754 cuts (Total 6799), LP: 142337347.879414 (27.39 seconds)
Found 32 exact subtours in 0.03 seconds
Add 32 cuts (Total 6831), LP: 142337347.879414 (1.44 seconds)
Add 28 cuts (Total 6817), LP: 142337347.898609 (3.65 seconds)
Found 14 exact subtours in 0.03 seconds
Add 14 cuts (Total 6831), LP: 142337347.898609 (1.30 seconds)
Found 4 exact subtours in 0.03 seconds
Add 4 cuts (Total 6835), LP: 142337347.898609 (1.05 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 6836), LP: 142337347.898609 (1.06 seconds)
Found 634 exact subtours in 0.52 seconds
Add 466 cuts (Total 7061), LP: 142337396.750994 (45.18 seconds)
Found 8 exact subtours in 0.03 seconds
Add 8 cuts (Total 7069), LP: 142337396.750994 (1.05 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7070), LP: 142337396.750994 (1.01 seconds)
Found 375 exact subtours in 0.49 seconds
Add 239 cuts (Total 7193), LP: 142337425.041518 (54.20 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7195), LP: 142337425.041518 (1.03 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7196), LP: 142337425.041518 (1.02 seconds)
Found 258 exact subtours in 0.48 seconds
Add 179 cuts (Total 7257), LP: 142337454.485669 (78.92 seconds)
Found 274 exact subtours in 0.41 seconds
Add 155 cuts (Total 7236), LP: 142337457.687275 (20.74 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7238), LP: 142337457.687275 (1.08 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7239), LP: 142337457.687275 (0.99 seconds)
Found 248 exact subtours in 0.55 seconds
Add 125 cuts (Total 7111), LP: 142337458.364360 (23.60 seconds)
Found 6 exact subtours in 0.02 seconds
Add 6 cuts (Total 7117), LP: 142337458.364360 (1.03 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7118), LP: 142337458.364360 (1.23 seconds)
Found 202 exact subtours in 0.47 seconds
Add 59 cuts (Total 7050), LP: 142337458.382769 (8.12 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7051), LP: 142337458.382769 (1.01 seconds)
Found 245 exact subtours in 0.50 seconds
Add 86 cuts (Total 6986), LP: 142337458.382918 (4.41 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 6988), LP: 142337458.382918 (1.04 seconds)
Found 1 exact subtours in 0.01 seconds
Add 1 cuts (Total 6989), LP: 142337458.382918 (1.02 seconds)
Found 1 exact subtours in 0.01 seconds
Add 1 cuts (Total 6990), LP: 142337458.382918 (1.00 seconds)
Found 285 exact subtours in 0.57 seconds
Add 125 cuts (Total 7115), LP: 142337458.382918 (2.43 seconds)
Found 195 exact subtours in 0.55 seconds
Add 36 cuts (Total 7151), LP: 142337458.382918 (1.54 seconds)
Found 170 exact subtours in 0.56 seconds
Add 11 cuts (Total 7162), LP: 142337458.382918 (1.34 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7163), LP: 142337458.382918 (1.04 seconds)
Found 164 exact subtours in 0.51 seconds
Add 5 cuts (Total 7168), LP: 142337458.382918 (1.29 seconds)
Found 164 exact subtours in 0.48 seconds
Add 5 cuts (Total 7173), LP: 142337458.382918 (1.28 seconds)
Found 170 exact subtours in 0.46 seconds
Add 11 cuts (Total 7184), LP: 142337458.382918 (1.09 seconds)
Found 161 exact subtours in 0.47 seconds
Add 2 cuts (Total 7186), LP: 142337458.382918 (1.00 seconds)
Found 163 exact subtours in 0.49 seconds
Add 4 cuts (Total 7190), LP: 142337458.382918 (1.20 seconds)
Found 162 exact subtours in 0.45 seconds
Add 3 cuts (Total 7193), LP: 142337458.382918 (1.06 seconds)
Found 162 exact subtours in 0.47 seconds
Add 3 cuts (Total 7196), LP: 142337458.382918 (1.06 seconds)
Found 161 exact subtours in 0.48 seconds
Add 2 cuts (Total 7198), LP: 142337458.382918 (1.16 seconds)
Found 161 exact subtours in 0.45 seconds
Add 2 cuts (Total 7200), LP: 142337458.382918 (1.10 seconds)
Found 161 exact subtours in 0.42 seconds
Add 2 cuts (Total 7202), LP: 142337458.382918 (1.12 seconds)
Found 161 exact subtours in 0.43 seconds
Add 2 cuts (Total 7204), LP: 142337458.382918 (1.16 seconds)
Found 161 exact subtours in 0.43 seconds
Add 2 cuts (Total 7071), LP: 142337483.334326 (28.12 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7072), LP: 142337483.334326 (1.01 seconds)
Found 149 exact subtours in 0.47 seconds
Add 16 cuts (Total 7035), LP: 142337483.997171 (6.00 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7036), LP: 142337483.997171 (0.97 seconds)
Found 154 exact subtours in 0.47 seconds
Add 21 cuts (Total 6919), LP: 142337486.899023 (40.75 seconds)
Found 5 exact subtours in 0.03 seconds
Add 5 cuts (Total 6924), LP: 142337486.899023 (0.99 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 6925), LP: 142337486.899023 (1.00 seconds)
Found 133 exact subtours in 0.46 seconds
Add 75 cuts (Total 7000), LP: 142337486.899023 (1.94 seconds)
Found 69 exact subtours in 0.40 seconds
Add 16 cuts (Total 7016), LP: 142337486.899023 (1.92 seconds)
Found 62 exact subtours in 0.38 seconds
Add 9 cuts (Total 7025), LP: 142337486.899023 (1.19 seconds)
Found 63 exact subtours in 0.40 seconds
Add 10 cuts (Total 7035), LP: 142337486.899023 (1.24 seconds)
Found 55 exact subtours in 0.44 seconds
Add 2 cuts (Total 7037), LP: 142337486.899023 (1.08 seconds)
Found 56 exact subtours in 0.37 seconds
Add 3 cuts (Total 7040), LP: 142337486.899023 (1.19 seconds)
Found 66 exact subtours in 0.39 seconds
Add 13 cuts (Total 7053), LP: 142337486.899023 (1.20 seconds)
Found 53 exact subtours in 0.38 seconds
Add 0 cuts (Total 7053), LP: 142337486.899023 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 5340, Ecount = 8709
Shrunk ecount = 8371, ncount = 5180
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 5180 nodes, and 8371 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 5180 nodes, and 8371 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 5 trivial dominos
GetDual: graph still has 54 extra paralel edges
GetDual: Not One Eliminated edges: 3
GetDual: Number of loops edges: 2
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3193 nodes and 16710 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 3
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 11580 dominoes.
Done.
DP Separator: Found 11585 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 949.410000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2515 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2717 combs) ...
Found 5000 domino cuts in 1094.52 seconds
Add 1871 cuts (Total 6877), LP: 142337493.556017 (143.71 seconds)
Added 1871 shrunk domino cuts
Found 279 tighten_lp cuts (max viol 2.0000) in 20.73 seconds
Add 263 cuts (Total 6819), LP: 142337519.049815 (67.92 seconds)
Found 52 CLOSE tighten_lp cuts (max viol 0.3637) in 1.91 seconds
Add 52 cuts (Total 6797), LP: 142337523.217506 (16.04 seconds)
Found 40 double deckers (max viol 4.0000) in 16.83 seconds
Add 40 cuts (Total 6787), LP: 142337523.269238 (5.48 seconds)
Found 9 CLOSE double deckers (max viol 1.0000) in 1.62 seconds
Add 9 cuts (Total 6796), LP: 142337523.269238 (1.59 seconds)
Found 914 consecutive ones cuts in 352.76 seconds
Add 734 cuts (Total 6820), LP: 142337524.020609 (25.78 seconds)
localcuts spheres(6d/8d)... 5262 nodes 8535 edges
localcuts done in 0.11 seconds
Found 2 localcuts in 0.11 seconds
Add 2 cuts (Total 6822), LP: 142337524.020609 (2.34 seconds)
localcuts spheres(7d/9d)... 5360 nodes 8664 edges
localcuts done in 0.11 seconds
Found 5 localcuts in 0.11 seconds
Add 5 cuts (Total 6827), LP: 142337524.020609 (1.54 seconds)
localcuts spheres(8d/10d)... 5400 nodes 8719 edges
localcuts done in 0.13 seconds
Found 9 localcuts in 0.13 seconds
Add 9 cuts (Total 6836), LP: 142337524.020609 (1.56 seconds)
localcuts spheres(9d/11d)... 5427 nodes 8764 edges
localcuts done in 0.13 seconds
Found 1 localcuts in 0.13 seconds
Add 1 cuts (Total 6837), LP: 142337524.020609 (1.61 seconds)
localcuts spheres(10d/12d)... 5414 nodes 8739 edges
localcuts done in 0.13 seconds
Found 6 localcuts in 0.13 seconds
Add 6 cuts (Total 6843), LP: 142337524.020609 (1.06 seconds)
localcuts spheres(11d/13d)... 5418 nodes 8745 edges
localcuts done in 0.13 seconds
Found 8 localcuts in 0.13 seconds
Add 8 cuts (Total 6851), LP: 142337524.020609 (1.11 seconds)
localcuts spheres(12d/14d)... 5413 nodes 8738 edges
localcuts done in 0.12 seconds
localcuts spheres(13d/15d)... 5413 nodes 8738 edges
localcuts done in 0.13 seconds
localcuts spheres(14d/16d)... 5413 nodes 8738 edges
localcuts done in 0.12 seconds
CCtsp_generate_edges (277700)
Time for Add edges optimize: 3.55 seconds (89.53 total in 6 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 8.59 seconds (114.52 total in 4 calls)
(SPARSE) 8 edges added, penalty -0.000000, val 142337524.020567
Time for Sparse edge check: 8.60 seconds (114.58 total in 4 calls)
Write Pool: 191525 cuts
Write Domino Pool: 1576 cuts
Time for Cutting inside loop: 2415.62 seconds (10137.56 total in 4 calls)
LP has: 92751 rows 169073 columns 882461 nonzeros
Loading lp...done in 0.82 seconds
LP has: 92751 rows 169073 columns 882455 nonzeros
Found 500 pool cuts (max viol 4.0000) in 0.96 seconds
Add 446 cuts (Total 7003), LP: 142337524.672768 (17.93 seconds)
Found 481 pool cuts (max viol 2.0579) in 0.95 seconds
Add 280 cuts (Total 6821), LP: 142337525.283528 (40.14 seconds)
Found 286 pool cuts (max viol 1.8143) in 0.96 seconds
Add 204 cuts (Total 6825), LP: 142337525.310104 (16.83 seconds)
Found 85 pool cuts (max viol 2.0000) in 1.02 seconds
Add 43 cuts (Total 6783), LP: 142337525.325058 (10.31 seconds)
Found 108 pool cuts (max viol 1.0529) in 0.96 seconds
Add 81 cuts (Total 6864), LP: 142337525.325058 (2.21 seconds)
Found 75 pool cuts (max viol 0.3081) in 0.96 seconds
Add 54 cuts (Total 6918), LP: 142337525.325058 (2.00 seconds)
Found 27 pool cuts (max viol 0.0020) in 0.96 seconds
Add 0 cuts (Total 6918), LP: 142337525.325058 (0.03 seconds)
Found 27 pool cuts (max viol 0.0020) in 0.97 seconds
Add 0 cuts (Total 6918), LP: 142337525.325058 (0.02 seconds)
Found 45 connect cuts in 0.02 seconds
Add 45 cuts (Total 6963), LP: 142337525.325058 (1.11 seconds)
Found 78 segment cuts in 0.13 seconds
Add 26 cuts (Total 6989), LP: 142337525.325058 (2.65 seconds)
Found 60 fast blossoms in 0.10 seconds
Add 60 cuts (Total 7049), LP: 142337525.325058 (1.19 seconds)
Found 62 Groetschel-Holland blossoms in 0.03 seconds
Add 60 cuts (Total 7109), LP: 142337525.325058 (2.76 seconds)
Block Combs
Type 0: 213 cuts 2.0000 max violation 0.57 seconds
Type 1: 172 cuts 2.0000 max violation 0.70 seconds
Type 2: 100 cuts 2.9987 max violation 0.75 seconds
Type 4: 66 cuts 1.9982 max violation 0.48 seconds
Type 5: 18 cuts 1.2222 max violation 2.15 seconds
Olaf 1: 127 cuts 2.0000 max violation 0.90 seconds
Olaf 2: 105 cuts 2.0000 max violation 1.12 seconds
Olaf 3: 86 cuts 2.0000 max violation 0.65 seconds
Olaf 4: 86 cuts 2.0000 max violation 0.81 seconds
Total Time in block_combs: 8.75
Found 973 block combs in 8.75 seconds
Add 543 cuts (Total 7163), LP: 142337525.329590 (19.06 seconds)
Found 16 exact subtours in 0.02 seconds
Add 16 cuts (Total 7179), LP: 142337525.329590 (1.44 seconds)
Add 16 cuts (Total 7175), LP: 142337529.677359 (11.40 seconds)
Found 7 exact subtours in 0.02 seconds
Add 7 cuts (Total 7182), LP: 142337529.677359 (1.04 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7183), LP: 142337529.677359 (1.07 seconds)
Found 514 exact subtours in 0.55 seconds
Add 367 cuts (Total 7232), LP: 142337530.505182 (37.13 seconds)
Found 8 exact subtours in 0.02 seconds
Add 8 cuts (Total 7240), LP: 142337530.505182 (1.23 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7241), LP: 142337530.505182 (1.06 seconds)
Found 389 exact subtours in 0.43 seconds
Add 254 cuts (Total 7149), LP: 142337531.292170 (38.59 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7151), LP: 142337531.292170 (1.22 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7152), LP: 142337531.292170 (1.02 seconds)
Found 324 exact subtours in 0.48 seconds
Add 204 cuts (Total 7132), LP: 142337531.317732 (16.02 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7135), LP: 142337531.317732 (1.03 seconds)
Found 204 exact subtours in 0.48 seconds
Add 77 cuts (Total 7156), LP: 142337531.488859 (24.47 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7157), LP: 142337531.488859 (1.03 seconds)
Found 141 exact subtours in 0.40 seconds
Add 47 cuts (Total 7204), LP: 142337531.488859 (1.95 seconds)
Found 131 exact subtours in 0.45 seconds
Add 36 cuts (Total 7240), LP: 142337531.488859 (1.38 seconds)
Found 107 exact subtours in 0.37 seconds
Add 6 cuts (Total 7246), LP: 142337531.488859 (1.27 seconds)
Found 106 exact subtours in 0.40 seconds
Add 5 cuts (Total 7251), LP: 142337531.488859 (1.21 seconds)
Found 104 exact subtours in 0.41 seconds
Add 3 cuts (Total 7254), LP: 142337531.488859 (1.22 seconds)
Found 104 exact subtours in 0.37 seconds
Add 3 cuts (Total 7257), LP: 142337531.488859 (1.15 seconds)
Found 104 exact subtours in 0.42 seconds
Add 2 cuts (Total 7259), LP: 142337531.488859 (1.20 seconds)
Found 103 exact subtours in 0.39 seconds
Add 2 cuts (Total 7261), LP: 142337531.488859 (1.03 seconds)
Found 104 exact subtours in 0.40 seconds
Add 3 cuts (Total 7264), LP: 142337531.488859 (1.03 seconds)
Found 102 exact subtours in 0.39 seconds
Add 1 cuts (Total 7265), LP: 142337531.488859 (1.03 seconds)
Found 103 exact subtours in 0.37 seconds
Add 2 cuts (Total 7267), LP: 142337531.488859 (1.01 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7270), LP: 142337531.488859 (1.04 seconds)
Found 102 exact subtours in 0.43 seconds
Add 1 cuts (Total 7271), LP: 142337531.488859 (1.02 seconds)
Found 104 exact subtours in 0.40 seconds
Add 3 cuts (Total 7274), LP: 142337531.488859 (1.04 seconds)
Found 103 exact subtours in 0.40 seconds
Add 2 cuts (Total 7276), LP: 142337531.488859 (1.08 seconds)
Found 102 exact subtours in 0.38 seconds
Add 1 cuts (Total 7277), LP: 142337531.488859 (1.10 seconds)
Found 103 exact subtours in 0.37 seconds
Add 2 cuts (Total 7279), LP: 142337531.488859 (1.04 seconds)
Found 101 exact subtours in 0.38 seconds
Add 0 cuts (Total 7279), LP: 142337531.488859 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 5498, Ecount = 9031
Shrunk ecount = 8681, ncount = 5345
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 5345 nodes, and 8681 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 5345 nodes, and 8681 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 4 trivial dominos
GetDual: graph still has 74 extra paralel edges
GetDual: Not One Eliminated edges: 1
GetDual: Number of loops edges: 0
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3338 nodes and 17338 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 4
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 12257 dominoes.
Done.
DP Separator: Found 12261 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 921.860000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2319 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2739 combs) ...
Found 5000 domino cuts in 1074.91 seconds
Add 1953 cuts (Total 7052), LP: 142337552.374472 (157.36 seconds)
Added 1953 shrunk domino cuts
Found 404 tighten_lp cuts (max viol 1.4000) in 23.79 seconds
Add 304 cuts (Total 7023), LP: 142337623.449224 (156.60 seconds)
Found 198 CLOSE tighten_lp cuts (max viol 0.4103) in 2.06 seconds
Add 198 cuts (Total 6965), LP: 142337644.892175 (75.31 seconds)
Found 72 double deckers (max viol 4.0000) in 19.03 seconds
Add 72 cuts (Total 6887), LP: 142337649.899229 (26.35 seconds)
Found 3 CLOSE double deckers (max viol 0.2372) in 2.36 seconds
Add 3 cuts (Total 6890), LP: 142337649.899229 (1.67 seconds)
Found 1011 consecutive ones cuts in 328.81 seconds
Add 666 cuts (Total 6957), LP: 142337657.775751 (51.07 seconds)
localcuts spheres(6d/8d)... 5434 nodes 8734 edges
localcuts done in 0.16 seconds
Found 8 localcuts in 0.16 seconds
Add 8 cuts (Total 6965), LP: 142337657.775751 (2.14 seconds)
localcuts spheres(7d/9d)... 5450 nodes 8755 edges
localcuts done in 0.17 seconds
Found 13 localcuts in 0.17 seconds
Add 13 cuts (Total 6978), LP: 142337657.775751 (2.42 seconds)
localcuts spheres(8d/10d)... 5454 nodes 8761 edges
localcuts done in 0.16 seconds
Found 11 localcuts in 0.16 seconds
Add 11 cuts (Total 6989), LP: 142337657.775751 (5.01 seconds)
localcuts spheres(9d/11d)... 5475 nodes 8793 edges
localcuts done in 0.16 seconds
Found 13 localcuts in 0.16 seconds
Add 13 cuts (Total 7002), LP: 142337657.775751 (5.33 seconds)
localcuts spheres(10d/12d)... 5393 nodes 8678 edges
localcuts done in 0.15 seconds
Found 6 localcuts in 0.15 seconds
Add 6 cuts (Total 7008), LP: 142337657.775751 (3.21 seconds)
localcuts spheres(11d/13d)... 5548 nodes 8895 edges
localcuts done in 0.20 seconds
Found 21 localcuts in 0.20 seconds
Add 21 cuts (Total 7029), LP: 142337657.775751 (4.19 seconds)
localcuts spheres(12d/14d)... 5505 nodes 8839 edges
localcuts done in 0.27 seconds
Found 30 localcuts in 0.27 seconds
Add 30 cuts (Total 7059), LP: 142337657.775751 (4.04 seconds)
localcuts spheres(13d/15d)... 5494 nodes 8833 edges
localcuts done in 1.27 seconds
Found 66 localcuts in 1.27 seconds
Add 66 cuts (Total 7125), LP: 142337657.775751 (9.84 seconds)
localcuts spheres(14d/16d)... 5530 nodes 8884 edges
localcuts done in 1.74 seconds
Found 160 localcuts in 1.74 seconds
Add 160 cuts (Total 7285), LP: 142337657.775751 (8.63 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 28.33 seconds (117.86 total in 7 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 34.24 seconds (148.76 total in 5 calls)
(SPARSE) 8 edges added, penalty -0.000000, val 142337650.163492
Time for Sparse edge check: 34.25 seconds (148.83 total in 5 calls)
Write Pool: 192130 cuts
Write Domino Pool: 1906 cuts
Time for Cutting inside loop: 2356.75 seconds (12494.31 total in 5 calls)
LP has: 93185 rows 169081 columns 938366 nonzeros
Loading lp...done in 1.05 seconds
LP has: 93185 rows 169081 columns 938348 nonzeros
Found 500 pool cuts (max viol 3.7506) in 0.97 seconds
Add 361 cuts (Total 6952), LP: 142337659.584587 (46.18 seconds)
Found 500 pool cuts (max viol 2.5000) in 0.98 seconds
Add 339 cuts (Total 6939), LP: 142337662.741057 (36.04 seconds)
Found 325 pool cuts (max viol 1.9977) in 0.97 seconds
Add 231 cuts (Total 6964), LP: 142337666.453813 (23.49 seconds)
Found 147 pool cuts (max viol 1.8255) in 0.97 seconds
Add 88 cuts (Total 6946), LP: 142337668.034346 (10.74 seconds)
Found 102 pool cuts (max viol 0.2933) in 0.97 seconds
Add 58 cuts (Total 6945), LP: 142337668.754820 (7.98 seconds)
Found 77 pool cuts (max viol 0.5264) in 0.98 seconds
Add 11 cuts (Total 6918), LP: 142337668.762718 (4.38 seconds)
Found 91 pool cuts (max viol 2.0000) in 0.98 seconds
Add 24 cuts (Total 6805), LP: 142337668.853567 (4.39 seconds)
Found 126 pool cuts (max viol 2.2845) in 0.98 seconds
Add 59 cuts (Total 6864), LP: 142337668.853567 (1.75 seconds)
Found 89 pool cuts (max viol 0.5000) in 0.99 seconds
Add 22 cuts (Total 6886), LP: 142337668.853567 (1.22 seconds)
Found 80 pool cuts (max viol 1.0000) in 0.97 seconds
Add 13 cuts (Total 6899), LP: 142337668.853567 (1.18 seconds)
Found 68 pool cuts (max viol 0.0074) in 0.98 seconds
Add 1 cuts (Total 6900), LP: 142337668.853567 (1.02 seconds)
Found 67 pool cuts (max viol 0.0018) in 0.98 seconds
Add 0 cuts (Total 6900), LP: 142337668.853567 (0.02 seconds)
Found 51 connect cuts in 0.02 seconds
Add 51 cuts (Total 6951), LP: 142337668.853567 (1.56 seconds)
Found 94 segment cuts in 0.12 seconds
Add 36 cuts (Total 6881), LP: 142337669.038215 (6.29 seconds)
Found 64 fast blossoms in 0.09 seconds
Add 64 cuts (Total 6945), LP: 142337669.038214 (2.07 seconds)
Found 64 Groetschel-Holland blossoms in 0.10 seconds
Add 61 cuts (Total 7006), LP: 142337669.038215 (2.39 seconds)
Block Combs
Type 0: 291 cuts 2.0000 max violation 0.77 seconds
Type 1: 185 cuts 2.0000 max violation 0.70 seconds
Type 2: 175 cuts 3.9946 max violation 0.69 seconds
Type 4: 95 cuts 1.9970 max violation 1.06 seconds
Type 5: 11 cuts 0.9936 max violation 1.44 seconds
Olaf 1: 172 cuts 2.0000 max violation 0.90 seconds
Olaf 2: 155 cuts 2.0000 max violation 1.00 seconds
Olaf 3: 56 cuts 1.9992 max violation 0.80 seconds
Olaf 4: 52 cuts 2.0000 max violation 0.78 seconds
Total Time in block_combs: 8.72
Found 1192 block combs in 8.72 seconds
Add 622 cuts (Total 6987), LP: 142337669.495858 (34.55 seconds)
Found 24 exact subtours in 0.03 seconds
Add 24 cuts (Total 7011), LP: 142337669.495858 (3.23 seconds)
Add 30 cuts (Total 7041), LP: 142337669.495858 (2.69 seconds)
Found 7 exact subtours in 0.03 seconds
Add 7 cuts (Total 7048), LP: 142337669.495858 (1.07 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7050), LP: 142337669.495858 (1.08 seconds)
Found 3 exact subtours in 0.02 seconds
Add 3 cuts (Total 7053), LP: 142337669.495858 (1.01 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7054), LP: 142337669.495858 (1.06 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7055), LP: 142337669.495858 (1.01 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 7057), LP: 142337669.495858 (1.05 seconds)
Found 681 exact subtours in 0.66 seconds
Add 465 cuts (Total 7181), LP: 142337669.643023 (22.67 seconds)
Found 7 exact subtours in 0.03 seconds
Add 7 cuts (Total 7188), LP: 142337669.643023 (1.07 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7191), LP: 142337669.643023 (0.99 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7192), LP: 142337669.643023 (1.04 seconds)
Found 422 exact subtours in 0.55 seconds
Add 259 cuts (Total 7451), LP: 142337669.643023 (9.15 seconds)
Found 245 exact subtours in 0.44 seconds
Add 86 cuts (Total 7303), LP: 142337683.125074 (35.55 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7305), LP: 142337683.125074 (1.08 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7306), LP: 142337683.125074 (1.05 seconds)
Found 267 exact subtours in 0.40 seconds
Add 100 cuts (Total 7406), LP: 142337683.125074 (2.92 seconds)
Found 196 exact subtours in 0.50 seconds
Add 26 cuts (Total 7432), LP: 142337683.125074 (1.72 seconds)
Found 181 exact subtours in 0.42 seconds
Add 13 cuts (Total 7445), LP: 142337683.125074 (1.30 seconds)
Found 180 exact subtours in 0.43 seconds
Add 9 cuts (Total 7454), LP: 142337683.125074 (1.23 seconds)
Found 177 exact subtours in 0.44 seconds
Add 6 cuts (Total 7460), LP: 142337683.125074 (1.35 seconds)
Found 175 exact subtours in 0.51 seconds
Add 4 cuts (Total 7464), LP: 142337683.125074 (1.03 seconds)
Found 174 exact subtours in 0.51 seconds
Add 3 cuts (Total 7467), LP: 142337683.125074 (1.04 seconds)
Found 174 exact subtours in 0.50 seconds
Add 3 cuts (Total 7470), LP: 142337683.125074 (1.33 seconds)
Found 176 exact subtours in 0.49 seconds
Add 5 cuts (Total 7475), LP: 142337683.125074 (1.69 seconds)
Found 175 exact subtours in 0.46 seconds
Add 5 cuts (Total 7480), LP: 142337683.125074 (1.38 seconds)
Found 176 exact subtours in 0.51 seconds
Add 5 cuts (Total 7485), LP: 142337683.125074 (1.12 seconds)
Found 174 exact subtours in 0.53 seconds
Add 3 cuts (Total 7488), LP: 142337683.125074 (1.21 seconds)
Found 171 exact subtours in 0.50 seconds
Add 0 cuts (Total 7488), LP: 142337683.125074 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 5903, Ecount = 9661
Shrunk ecount = 9335, ncount = 5762
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 5762 nodes, and 9335 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 5762 nodes, and 9335 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 5 trivial dominos
GetDual: graph still has 70 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 4
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3575 nodes and 18646 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 5
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 13872 dominoes.
Done.
DP Separator: Found 13877 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 949.250000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 1068 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (1911 combs) ...
Found 5000 domino cuts in 1129.90 seconds
Add 1536 cuts (Total 9024), LP: 142337683.125074 (98.67 seconds)
Added 1536 shrunk domino cuts
Found 399 tighten_lp cuts (max viol 1.0000) in 15.41 seconds
Add 282 cuts (Total 7707), LP: 142337689.346888 (150.72 seconds)
Found 97 CLOSE tighten_lp cuts (max viol 0.9995) in 1.77 seconds
Add 97 cuts (Total 7717), LP: 142337690.856526 (47.45 seconds)
Found 171 double deckers (max viol 2.0000) in 14.23 seconds
Add 171 cuts (Total 7795), LP: 142337705.075261 (86.43 seconds)
Found 5 CLOSE double deckers (max viol 0.4545) in 2.07 seconds
Add 5 cuts (Total 7800), LP: 142337705.075261 (1.38 seconds)
Found 662 consecutive ones cuts in 271.22 seconds
Add 539 cuts (Total 7487), LP: 142337712.991643 (143.29 seconds)
localcuts spheres(6d/8d)... 6600 nodes 10666 edges
localcuts done in 0.27 seconds
Found 43 localcuts in 0.27 seconds
Add 43 cuts (Total 7530), LP: 142337712.991643 (6.94 seconds)
localcuts spheres(7d/9d)... 6644 nodes 10741 edges
localcuts done in 0.67 seconds
Found 76 localcuts in 0.67 seconds
Add 76 cuts (Total 7606), LP: 142337712.991643 (8.87 seconds)
localcuts spheres(8d/10d)... 6749 nodes 10894 edges
localcuts done in 0.34 seconds
Found 58 localcuts in 0.34 seconds
Add 58 cuts (Total 7664), LP: 142337712.991643 (4.46 seconds)
localcuts spheres(9d/11d)... 6711 nodes 10831 edges
localcuts done in 0.38 seconds
Found 40 localcuts in 0.38 seconds
Add 40 cuts (Total 7704), LP: 142337712.991643 (3.73 seconds)
localcuts spheres(10d/12d)... 6760 nodes 10909 edges
localcuts done in 0.39 seconds
Found 40 localcuts in 0.39 seconds
Add 40 cuts (Total 7744), LP: 142337712.991643 (4.67 seconds)
localcuts spheres(11d/13d)... 6728 nodes 10852 edges
localcuts done in 0.42 seconds
Found 44 localcuts in 0.42 seconds
Add 44 cuts (Total 7788), LP: 142337712.991643 (3.30 seconds)
localcuts spheres(12d/14d)... 6646 nodes 10747 edges
localcuts done in 0.53 seconds
Found 56 localcuts in 0.53 seconds
Add 56 cuts (Total 7844), LP: 142337712.991643 (3.99 seconds)
localcuts spheres(13d/15d)... 6772 nodes 10919 edges
localcuts done in 2.21 seconds
Found 65 localcuts in 2.21 seconds
Add 65 cuts (Total 7552), LP: 142337712.991643 (8.88 seconds)
localcuts spheres(14d/16d)... 6542 nodes 10566 edges
localcuts done in 0.26 seconds
Found 11 localcuts in 0.26 seconds
Add 11 cuts (Total 7563), LP: 142337712.991643 (1.36 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 101.68 seconds (219.54 total in 8 calls)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.35 seconds (220.89 total in 9 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 111.12 seconds (259.88 total in 6 calls)
(SPARSE) 7 edges added, penalty -0.000000, val 142337712.415661
Time for Sparse edge check: 111.13 seconds (259.96 total in 6 calls)
Write Pool: 193051 cuts
Write Domino Pool: 2154 cuts
Time for Cutting inside loop: 2495.20 seconds (14989.51 total in 6 calls)
LP has: 93463 rows 169088 columns 925816 nonzeros
Loading lp...done in 0.97 seconds
LP has: 93463 rows 169088 columns 925816 nonzeros
Found 500 pool cuts (max viol 3.3007) in 0.98 seconds
Add 339 cuts (Total 7201), LP: 142337715.194167 (56.37 seconds)
Found 500 pool cuts (max viol 3.8696) in 0.98 seconds
Add 322 cuts (Total 6902), LP: 142337717.068669 (44.90 seconds)
Found 371 pool cuts (max viol 4.0000) in 0.99 seconds
Add 272 cuts (Total 6875), LP: 142337717.072398 (11.73 seconds)
Found 161 pool cuts (max viol 1.5025) in 1.00 seconds
Add 111 cuts (Total 6843), LP: 142337717.075176 (5.65 seconds)
Found 87 pool cuts (max viol 1.0000) in 0.95 seconds
Add 43 cuts (Total 6886), LP: 142337717.075176 (1.55 seconds)
Found 46 pool cuts (max viol 1.0000) in 0.95 seconds
Add 6 cuts (Total 6892), LP: 142337717.075176 (1.14 seconds)
Found 40 pool cuts (max viol 0.0017) in 1.00 seconds
Add 0 cuts (Total 6892), LP: 142337717.075176 (0.03 seconds)
Found 61 connect cuts in 0.04 seconds
Add 61 cuts (Total 6953), LP: 142337717.075176 (1.54 seconds)
Found 72 segment cuts in 0.13 seconds
Add 52 cuts (Total 6891), LP: 142337720.292831 (18.21 seconds)
Found 60 fast blossoms in 0.11 seconds
Add 60 cuts (Total 6951), LP: 142337720.292831 (1.73 seconds)
Found 59 Groetschel-Holland blossoms in 0.08 seconds
Add 57 cuts (Total 7008), LP: 142337720.292831 (2.75 seconds)
Block Combs
Type 0: 264 cuts 2.0000 max violation 0.61 seconds
Type 1: 177 cuts 1.9954 max violation 0.73 seconds
Type 2: 168 cuts 1.9982 max violation 0.58 seconds
Type 4: 112 cuts 1.9976 max violation 0.64 seconds
Type 5: 14 cuts 1.9868 max violation 1.08 seconds
Olaf 1: 148 cuts 1.9954 max violation 0.86 seconds
Olaf 2: 124 cuts 2.0000 max violation 0.92 seconds
Olaf 3: 84 cuts 1.9989 max violation 0.71 seconds
Olaf 4: 112 cuts 1.9989 max violation 0.75 seconds
Total Time in block_combs: 7.52
Found 1203 block combs in 7.52 seconds
Add 688 cuts (Total 7125), LP: 142337720.516224 (36.64 seconds)
Found 20 exact subtours in 0.03 seconds
Add 20 cuts (Total 7145), LP: 142337720.516224 (2.66 seconds)
Add 17 cuts (Total 7040), LP: 142337722.117083 (26.43 seconds)
Found 8 exact subtours in 0.02 seconds
Add 8 cuts (Total 7048), LP: 142337722.117083 (1.24 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 7050), LP: 142337722.117083 (1.04 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7051), LP: 142337722.117083 (1.24 seconds)
Found 683 exact subtours in 0.70 seconds
Add 452 cuts (Total 7135), LP: 142337722.636483 (43.92 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7138), LP: 142337722.636483 (1.12 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7140), LP: 142337722.636483 (1.05 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7141), LP: 142337722.636483 (1.09 seconds)
Found 499 exact subtours in 0.46 seconds
Add 268 cuts (Total 7409), LP: 142337722.636483 (10.20 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7410), LP: 142337722.636483 (1.06 seconds)
Found 291 exact subtours in 0.51 seconds
Add 95 cuts (Total 7505), LP: 142337722.636483 (4.54 seconds)
Found 240 exact subtours in 0.45 seconds
Add 43 cuts (Total 7548), LP: 142337722.636483 (2.34 seconds)
Found 218 exact subtours in 0.38 seconds
Add 18 cuts (Total 7566), LP: 142337722.636483 (1.79 seconds)
Found 210 exact subtours in 0.40 seconds
Add 11 cuts (Total 7577), LP: 142337722.636483 (1.74 seconds)
Found 211 exact subtours in 0.41 seconds
Add 12 cuts (Total 7589), LP: 142337722.636483 (1.74 seconds)
Found 205 exact subtours in 0.41 seconds
Add 6 cuts (Total 7595), LP: 142337722.636483 (1.51 seconds)
Found 204 exact subtours in 0.40 seconds
Add 5 cuts (Total 7600), LP: 142337722.636483 (1.24 seconds)
Found 205 exact subtours in 0.39 seconds
Add 6 cuts (Total 7606), LP: 142337722.636483 (1.56 seconds)
Found 202 exact subtours in 0.39 seconds
Add 3 cuts (Total 7609), LP: 142337722.636483 (1.24 seconds)
Found 202 exact subtours in 0.40 seconds
Add 3 cuts (Total 7612), LP: 142337722.636483 (1.29 seconds)
Found 202 exact subtours in 0.39 seconds
Add 3 cuts (Total 7615), LP: 142337722.636483 (1.29 seconds)
Found 202 exact subtours in 0.41 seconds
Add 3 cuts (Total 7618), LP: 142337722.636483 (1.35 seconds)
Found 200 exact subtours in 0.40 seconds
Add 1 cuts (Total 7619), LP: 142337722.636483 (1.16 seconds)
Found 200 exact subtours in 0.40 seconds
Add 1 cuts (Total 7620), LP: 142337722.636483 (1.23 seconds)
Found 200 exact subtours in 0.40 seconds
Add 1 cuts (Total 7621), LP: 142337722.636483 (1.09 seconds)
Found 201 exact subtours in 0.40 seconds
Add 2 cuts (Total 7623), LP: 142337722.636483 (1.24 seconds)
Found 200 exact subtours in 0.40 seconds
Add 1 cuts (Total 7624), LP: 142337722.636483 (1.11 seconds)
Found 200 exact subtours in 0.49 seconds
Add 1 cuts (Total 7625), LP: 142337722.636483 (1.05 seconds)
Found 200 exact subtours in 0.47 seconds
Add 1 cuts (Total 7626), LP: 142337722.636483 (1.06 seconds)
Found 200 exact subtours in 0.48 seconds
Add 1 cuts (Total 7627), LP: 142337722.636483 (1.13 seconds)
Found 199 exact subtours in 0.49 seconds
Add 0 cuts (Total 7627), LP: 142337722.636483 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 6234, Ecount = 10262
Shrunk ecount = 9802, ncount = 6019
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6019 nodes, and 9802 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6019 nodes, and 9802 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 4 trivial dominos
GetDual: graph still has 76 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 4
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3785 nodes and 19582 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 6
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 14156 dominoes.
Done.
DP Separator: Found 14160 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 983.200000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2451 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (3124 combs) ...
Found 5000 domino cuts in 1173.00 seconds
Add 1457 cuts (Total 9084), LP: 142337722.636483 (76.02 seconds)
Added 1457 shrunk domino cuts
Found 500 tighten_lp cuts (max viol 1.0000) in 18.25 seconds
Add 384 cuts (Total 7773), LP: 142337729.744752 (201.39 seconds)
Found 46 CLOSE tighten_lp cuts (max viol 0.3111) in 1.82 seconds
Add 46 cuts (Total 7771), LP: 142337730.041909 (42.87 seconds)
Found 204 double deckers (max viol 2.0000) in 13.87 seconds
Add 204 cuts (Total 7975), LP: 142337730.041909 (38.57 seconds)
Found 9 CLOSE double deckers (max viol 0.2500) in 2.03 seconds
Add 9 cuts (Total 7984), LP: 142337730.041909 (1.51 seconds)
Found 1126 consecutive ones cuts in 267.96 seconds
Add 612 cuts (Total 8596), LP: 142337730.041909 (49.79 seconds)
localcuts spheres(6d/8d)... 6463 nodes 10568 edges
localcuts done in 2.47 seconds
Found 260 localcuts in 2.47 seconds
Add 258 cuts (Total 8854), LP: 142337730.041909 (29.41 seconds)
localcuts spheres(7d/9d)... 6497 nodes 10626 edges
localcuts done in 2.85 seconds
Found 330 localcuts in 2.85 seconds
Add 327 cuts (Total 8088), LP: 142337730.150323 (45.09 seconds)
localcuts spheres(8d/10d)... 6585 nodes 10768 edges
localcuts done in 0.19 seconds
Found 12 localcuts in 0.19 seconds
Add 12 cuts (Total 8100), LP: 142337730.150323 (6.35 seconds)
localcuts spheres(9d/11d)... 6584 nodes 10777 edges
localcuts done in 0.22 seconds
Found 22 localcuts in 0.22 seconds
Add 22 cuts (Total 8122), LP: 142337730.150323 (7.01 seconds)
localcuts spheres(10d/12d)... 6547 nodes 10714 edges
localcuts done in 0.18 seconds
Found 7 localcuts in 0.18 seconds
Add 7 cuts (Total 8129), LP: 142337730.150323 (5.54 seconds)
localcuts spheres(11d/13d)... 6510 nodes 10664 edges
localcuts done in 0.34 seconds
Found 33 localcuts in 0.34 seconds
Add 33 cuts (Total 8162), LP: 142337730.150323 (11.64 seconds)
localcuts spheres(12d/14d)... 6361 nodes 10423 edges
localcuts done in 1.18 seconds
Found 137 localcuts in 1.18 seconds
Add 137 cuts (Total 8299), LP: 142337730.150323 (17.78 seconds)
localcuts spheres(13d/15d)... 6505 nodes 10649 edges
localcuts done in 1.40 seconds
Found 103 localcuts in 1.40 seconds
Add 103 cuts (Total 8402), LP: 142337730.150323 (15.27 seconds)
localcuts spheres(14d/16d)... 6549 nodes 10725 edges
localcuts done in 0.43 seconds
Found 27 localcuts in 0.43 seconds
Add 27 cuts (Total 8429), LP: 142337730.150323 (6.42 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 56.73 seconds (277.62 total in 10 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 62.14 seconds (322.02 total in 7 calls)
(SPARSE) 4 edges added, penalty -0.000000, val 142337729.055828
Time for Sparse edge check: 62.15 seconds (322.11 total in 7 calls)
Write Pool: 194025 cuts
Write Domino Pool: 2454 cuts
Time for Cutting inside loop: 2496.13 seconds (17485.64 total in 7 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 6.54 seconds (284.16 total in 11 calls)
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 32.38 seconds (354.40 total in 8 calls)
8 edges added, penalty -0.000000
New lower bound: 142337729.055824
Time for Full edge check: 32.41 seconds (32.41 total in 1 calls)
Setting tolerances: next cuts 459.7494 next round 45.9749
LP has: 94329 rows 169100 columns 984610 nonzeros
Loading lp...done in 1.01 seconds
LP has: 94329 rows 169100 columns 984605 nonzeros
Found 500 pool cuts (max viol 2.0000) in 1.02 seconds
Add 348 cuts (Total 8008), LP: 142337729.869186 (59.14 seconds)
Found 482 pool cuts (max viol 2.5000) in 1.02 seconds
Add 376 cuts (Total 7988), LP: 142337731.151891 (57.19 seconds)
Found 190 pool cuts (max viol 1.0000) in 0.99 seconds
Add 135 cuts (Total 7853), LP: 142337731.175588 (22.90 seconds)
Found 158 pool cuts (max viol 1.9974) in 1.04 seconds
Add 118 cuts (Total 7971), LP: 142337731.175588 (6.83 seconds)
Found 62 pool cuts (max viol 0.5423) in 1.01 seconds
Add 30 cuts (Total 7268), LP: 142337731.175894 (9.13 seconds)
Found 137 pool cuts (max viol 4.0000) in 1.02 seconds
Add 94 cuts (Total 7362), LP: 142337731.175894 (2.49 seconds)
Found 59 pool cuts (max viol 1.0000) in 0.98 seconds
Add 20 cuts (Total 7228), LP: 142337731.177077 (5.51 seconds)
Found 77 pool cuts (max viol 3.6352) in 1.02 seconds
Add 39 cuts (Total 7267), LP: 142337731.177077 (1.31 seconds)
Found 45 pool cuts (max viol 1.0000) in 1.14 seconds
Add 7 cuts (Total 7274), LP: 142337731.177077 (1.29 seconds)
Found 38 pool cuts (max viol 0.0019) in 1.01 seconds
Add 0 cuts (Total 7274), LP: 142337731.177077 (0.01 seconds)
Found 41 connect cuts in 0.03 seconds
Add 41 cuts (Total 7315), LP: 142337731.177077 (1.17 seconds)
Found 68 segment cuts in 0.14 seconds
Add 47 cuts (Total 7362), LP: 142337731.177077 (3.91 seconds)
Found 60 fast blossoms in 0.10 seconds
Add 60 cuts (Total 7422), LP: 142337731.177077 (2.23 seconds)
Found 58 Groetschel-Holland blossoms in 0.08 seconds
Add 55 cuts (Total 7477), LP: 142337731.177077 (3.61 seconds)
Block Combs
Type 0: 249 cuts 1.9999 max violation 0.95 seconds
Type 1: 204 cuts 1.9997 max violation 0.87 seconds
Type 2: 116 cuts 1.9997 max violation 0.51 seconds
Type 3: 89 cuts 1.9997 max violation 0.52 seconds
Type 4: 93 cuts 1.9988 max violation 0.43 seconds
Type 5: 12 cuts 1.2139 max violation 1.48 seconds
Olaf 1: 120 cuts 1.9999 max violation 1.00 seconds
Olaf 2: 124 cuts 1.9999 max violation 1.17 seconds
Olaf 3: 89 cuts 2.5396 max violation 1.07 seconds
Olaf 4: 75 cuts 1.9998 max violation 1.25 seconds
Total Time in block_combs: 9.89
Found 1171 block combs in 9.89 seconds
Add 674 cuts (Total 7210), LP: 142337731.182101 (27.71 seconds)
Found 26 exact subtours in 0.03 seconds
Add 26 cuts (Total 7236), LP: 142337731.182101 (2.84 seconds)
Add 13 cuts (Total 7249), LP: 142337731.182101 (2.06 seconds)
Found 6 exact subtours in 0.04 seconds
Add 6 cuts (Total 7255), LP: 142337731.182101 (1.37 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7256), LP: 142337731.182101 (1.04 seconds)
Found 648 exact subtours in 0.61 seconds
Add 471 cuts (Total 7727), LP: 142337731.182101 (22.91 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7728), LP: 142337731.182101 (1.13 seconds)
Found 359 exact subtours in 0.61 seconds
Add 222 cuts (Total 7572), LP: 142337731.500855 (11.02 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7574), LP: 142337731.500855 (1.09 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7575), LP: 142337731.500855 (1.09 seconds)
Found 211 exact subtours in 0.55 seconds
Add 79 cuts (Total 7654), LP: 142337731.500855 (4.17 seconds)
Found 165 exact subtours in 0.54 seconds
Add 35 cuts (Total 7689), LP: 142337731.500854 (3.53 seconds)
Found 156 exact subtours in 0.58 seconds
Add 21 cuts (Total 7451), LP: 142337731.500855 (5.85 seconds)
Found 5 exact subtours in 0.03 seconds
Add 5 cuts (Total 7456), LP: 142337731.500855 (1.65 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7457), LP: 142337731.500855 (1.63 seconds)
Found 191 exact subtours in 0.54 seconds
Add 55 cuts (Total 7512), LP: 142337731.500855 (3.07 seconds)
Found 164 exact subtours in 0.58 seconds
Add 29 cuts (Total 7541), LP: 142337731.500856 (2.72 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7542), LP: 142337731.500855 (1.08 seconds)
Found 143 exact subtours in 0.51 seconds
Add 8 cuts (Total 7550), LP: 142337731.500855 (2.83 seconds)
Found 147 exact subtours in 0.50 seconds
Add 13 cuts (Total 7563), LP: 142337731.500855 (1.80 seconds)
Found 136 exact subtours in 0.59 seconds
Add 1 cuts (Total 7564), LP: 142337731.500855 (1.03 seconds)
Found 134 exact subtours in 0.62 seconds
Add 0 cuts (Total 7564), LP: 142337731.500855 (0.04 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 5840, Ecount = 9586
Shrunk ecount = 9215, ncount = 5687
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 5687 nodes, and 9215 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 5687 nodes, and 9215 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 3 trivial dominos
GetDual: graph still has 84 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 5
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3530 nodes and 18412 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 7
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 13299 dominoes.
Done.
DP Separator: Found 13302 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 981.050000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 1864 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2785 combs) ...
Found 5000 domino cuts in 1144.56 seconds
Add 2030 cuts (Total 9594), LP: 142337731.500855 (211.13 seconds)
Added 2030 shrunk domino cuts
Found 255 tighten_lp cuts (max viol 1.3998) in 15.03 seconds
Add 251 cuts (Total 7855), LP: 142337732.592051 (65.18 seconds)
Found 23 CLOSE tighten_lp cuts (max viol 0.2328) in 1.83 seconds
Add 23 cuts (Total 7812), LP: 142337733.369423 (13.76 seconds)
Found 191 double deckers (max viol 4.0000) in 15.22 seconds
Add 191 cuts (Total 8003), LP: 142337733.369423 (22.30 seconds)
Found 1 CLOSE double deckers (max viol 0.0833) in 2.12 seconds
Add 1 cuts (Total 8004), LP: 142337733.369423 (1.13 seconds)
Found 514 consecutive ones cuts in 213.42 seconds
Add 425 cuts (Total 7994), LP: 142337734.134300 (59.75 seconds)
localcuts spheres(6d/8d)... 6807 nodes 11023 edges
localcuts done in 0.71 seconds
Found 76 localcuts in 0.71 seconds
Add 76 cuts (Total 8070), LP: 142337734.134300 (13.27 seconds)
localcuts spheres(7d/9d)... 6789 nodes 10992 edges
localcuts done in 0.78 seconds
Found 68 localcuts in 0.78 seconds
Add 68 cuts (Total 8138), LP: 142337734.134300 (18.23 seconds)
localcuts spheres(8d/10d)... 6798 nodes 11032 edges
localcuts done in 0.88 seconds
Found 67 localcuts in 0.88 seconds
Add 67 cuts (Total 8205), LP: 142337734.134300 (21.02 seconds)
localcuts spheres(9d/11d)... 6773 nodes 10989 edges
localcuts done in 1.08 seconds
Found 100 localcuts in 1.08 seconds
Add 100 cuts (Total 8305), LP: 142337734.134300 (17.32 seconds)
localcuts spheres(10d/12d)... 6852 nodes 11124 edges
localcuts done in 1.79 seconds
Found 284 localcuts in 1.79 seconds
Add 275 cuts (Total 8580), LP: 142337734.134300 (19.15 seconds)
localcuts spheres(11d/13d)... 6932 nodes 11252 edges
localcuts done in 2.48 seconds
Found 265 localcuts in 2.48 seconds
Add 263 cuts (Total 8843), LP: 142337734.134300 (38.09 seconds)
localcuts spheres(12d/14d)... 6950 nodes 11284 edges
localcuts done in 2.87 seconds
Found 282 localcuts in 2.87 seconds
Add 281 cuts (Total 9124), LP: 142337734.134293 (31.85 seconds)
localcuts spheres(13d/15d)... 7045 nodes 11438 edges
localcuts done in 3.58 seconds
Found 181 localcuts in 3.58 seconds
Add 181 cuts (Total 8289), LP: 142337734.134300 (32.50 seconds)
localcuts spheres(14d/16d)... 7056 nodes 11440 edges
localcuts done in 3.33 seconds
Found 189 localcuts in 3.33 seconds
Add 189 cuts (Total 8478), LP: 142337734.134300 (21.81 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 8.36 seconds (292.52 total in 12 calls)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 0.79 seconds (293.31 total in 13 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 18.07 seconds (372.47 total in 9 calls)
(SPARSE) 5 edges added, penalty -0.000000, val 142337734.116615
Time for Sparse edge check: 18.09 seconds (340.20 total in 8 calls)
Write Pool: 195101 cuts
Write Domino Pool: 2781 cuts
Time for Cutting inside loop: 2389.48 seconds (19875.12 total in 8 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.24 seconds (294.55 total in 14 calls)
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 27.50 seconds (399.97 total in 10 calls)
1 edges added, penalty -0.000000
New lower bound: 142337734.116615
Time for Full edge check: 27.52 seconds (59.93 total in 2 calls)
Time for Cutting Loop: 19938.98 seconds (19938.98 total in 1 calls)
Number of outside rounds: 2
SETTING MAXCHUNKSIZE = 20
Setting tolerances: next cuts 459.6988 next round 45.9699
CCtsp_init_edgegenerator (50)
..................................................................................... 2361757 edges
LP has: 94378 rows 169106 columns 974912 nonzeros
Loading lp...done in 1.13 seconds
LP has: 94378 rows 169106 columns 974910 nonzeros
Found 500 pool cuts (max viol 3.6911) in 1.00 seconds
Add 361 cuts (Total 8839), LP: 142337734.116615 (49.36 seconds)
Found 284 pool cuts (max viol 1.3333) in 1.03 seconds
Add 243 cuts (Total 9082), LP: 142337734.116615 (14.24 seconds)
Found 135 pool cuts (max viol 1.0000) in 1.03 seconds
Add 95 cuts (Total 8596), LP: 142337734.117697 (11.22 seconds)
Found 70 pool cuts (max viol 3.8861) in 1.03 seconds
Add 44 cuts (Total 8640), LP: 142337734.117697 (3.20 seconds)
Found 30 pool cuts (max viol 0.0523) in 1.02 seconds
Add 6 cuts (Total 8646), LP: 142337734.117697 (1.77 seconds)
Found 37 pool cuts (max viol 1.2000) in 1.04 seconds
Add 12 cuts (Total 8658), LP: 142337734.117697 (1.13 seconds)
Found 24 pool cuts (max viol 0.0020) in 1.02 seconds
Add 0 cuts (Total 8658), LP: 142337734.117697 (0.01 seconds)
Found 3 connect cuts in 0.03 seconds
Add 3 cuts (Total 8661), LP: 142337734.117697 (1.17 seconds)
Found 45 segment cuts in 0.11 seconds
Add 32 cuts (Total 8274), LP: 142337734.122968 (11.83 seconds)
Found 52 fast blossoms in 0.09 seconds
Add 52 cuts (Total 8326), LP: 142337734.122968 (12.05 seconds)
Found 54 Groetschel-Holland blossoms in 0.08 seconds
Add 52 cuts (Total 8378), LP: 142337734.122968 (17.86 seconds)
Block Combs
Type 0: 296 cuts 2.0000 max violation 0.66 seconds
Type 1: 221 cuts 2.0000 max violation 0.68 seconds
Type 2: 181 cuts 1.9917 max violation 0.51 seconds
Type 4: 137 cuts 1.4739 max violation 0.45 seconds
Type 5: 30 cuts 0.8389 max violation 1.96 seconds
Olaf 1: 120 cuts 1.0000 max violation 0.88 seconds
Olaf 2: 114 cuts 1.0000 max violation 1.06 seconds
Olaf 3: 63 cuts 1.6844 max violation 1.15 seconds
Olaf 4: 61 cuts 1.6844 max violation 1.05 seconds
Total Time in block_combs: 9.07
Found 1223 block combs in 9.07 seconds
Add 653 cuts (Total 8190), LP: 142337734.141422 (76.40 seconds)
Found 13 exact subtours in 0.03 seconds
Add 13 cuts (Total 8203), LP: 142337734.141422 (2.22 seconds)
Add 10 cuts (Total 8213), LP: 142337734.141422 (2.13 seconds)
Found 6 exact subtours in 0.03 seconds
Add 6 cuts (Total 8219), LP: 142337734.141422 (1.17 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8220), LP: 142337734.141422 (1.10 seconds)
Found 527 exact subtours in 0.73 seconds
Add 349 cuts (Total 8569), LP: 142337734.141422 (52.89 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8570), LP: 142337734.141422 (15.78 seconds)
Found 313 exact subtours in 0.47 seconds
Add 174 cuts (Total 8744), LP: 142337734.141422 (20.35 seconds)
Found 222 exact subtours in 0.57 seconds
Add 86 cuts (Total 8830), LP: 142337734.141422 (17.72 seconds)
Found 180 exact subtours in 0.62 seconds
Add 57 cuts (Total 8887), LP: 142337734.141422 (8.74 seconds)
Found 149 exact subtours in 0.64 seconds
Add 28 cuts (Total 8915), LP: 142337734.141422 (7.97 seconds)
Found 143 exact subtours in 0.57 seconds
Add 8 cuts (Total 8923), LP: 142337734.141422 (2.76 seconds)
Found 138 exact subtours in 0.53 seconds
Add 3 cuts (Total 8926), LP: 142337734.141422 (1.54 seconds)
Found 135 exact subtours in 0.57 seconds
Add 0 cuts (Total 8926), LP: 142337734.141422 (0.01 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 6766, Ecount = 11107
Shrunk ecount = 10767, ncount = 6617
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6617 nodes, and 10767 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6617 nodes, and 10767 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 6 trivial dominos
GetDual: graph still has 72 extra paralel edges
GetDual: Not One Eliminated edges: 2
GetDual: Number of loops edges: 1
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 4152 nodes and 21506 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 8
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 16190 dominoes.
Done.
DP Separator: Found 16196 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 996.570000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2253 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (2956 combs) ...
Found 5000 domino cuts in 1226.61 seconds
Add 1925 cuts (Total 10851), LP: 142337734.141422 (404.88 seconds)
Added 1925 shrunk domino cuts
Found 362 tighten_lp cuts (max viol 1.0000) in 16.07 seconds
Add 311 cuts (Total 9000), LP: 142337734.539321 (192.17 seconds)
Found 24 CLOSE tighten_lp cuts (max viol 0.4997) in 1.93 seconds
Add 24 cuts (Total 8476), LP: 142337734.589490 (20.42 seconds)
Found 419 double deckers (max viol 2.9869) in 15.46 seconds
Add 359 cuts (Total 8835), LP: 142337734.589490 (89.24 seconds)
Found 14 CLOSE double deckers (max viol 0.2626) in 2.46 seconds
Add 14 cuts (Total 8849), LP: 142337734.589490 (6.02 seconds)
Found 474 consecutive ones cuts in 193.75 seconds
Add 384 cuts (Total 9233), LP: 142337734.589490 (64.93 seconds)
localcuts classes(8d)... 7422 nodes 11953 edges
localcuts done in 0.22 seconds
Found 20 localcuts in 0.22 seconds
Add 20 cuts (Total 9253), LP: 142337734.589490 (14.63 seconds)
localcuts classes(9d)... 7487 nodes 12057 edges
localcuts done in 0.23 seconds
Found 26 localcuts in 0.23 seconds
Add 26 cuts (Total 9279), LP: 142337734.589490 (18.16 seconds)
localcuts classes(10d)... 7408 nodes 11944 edges
localcuts done in 0.25 seconds
Found 22 localcuts in 0.25 seconds
Add 22 cuts (Total 9301), LP: 142337734.589490 (14.12 seconds)
localcuts classes(11d)... 7476 nodes 12056 edges
localcuts done in 0.26 seconds
Found 20 localcuts in 0.26 seconds
Add 20 cuts (Total 9321), LP: 142337734.589490 (6.43 seconds)
localcuts classes(12d)... 7562 nodes 12191 edges
localcuts done in 0.27 seconds
Found 26 localcuts in 0.27 seconds
Add 26 cuts (Total 9347), LP: 142337734.589490 (14.70 seconds)
localcuts classes(13d)... 7610 nodes 12261 edges
localcuts done in 0.29 seconds
Found 21 localcuts in 0.29 seconds
Add 21 cuts (Total 8942), LP: 142337734.610368 (24.23 seconds)
localcuts classes(14d)... 7674 nodes 12383 edges
localcuts done in 0.34 seconds
Found 28 localcuts in 0.34 seconds
Add 28 cuts (Total 8970), LP: 142337734.610368 (14.24 seconds)
localcuts classes(15d)... 7716 nodes 12460 edges
localcuts done in 0.95 seconds
Found 21 localcuts in 0.95 seconds
Add 21 cuts (Total 8991), LP: 142337734.610368 (17.93 seconds)
localcuts classes(16d)... 7786 nodes 12570 edges
localcuts done in 0.76 seconds
Found 22 localcuts in 0.76 seconds
Add 22 cuts (Total 9013), LP: 142337734.610368 (23.31 seconds)
localcuts classes(17d)... 7534 nodes 12208 edges
localcuts done in 0.40 seconds
Found 24 localcuts in 0.40 seconds
Add 24 cuts (Total 9037), LP: 142337734.610368 (13.33 seconds)
localcuts classes(18d)... 7603 nodes 12299 edges
localcuts done in 0.62 seconds
Found 18 localcuts in 0.62 seconds
Add 18 cuts (Total 9055), LP: 142337734.610368 (15.87 seconds)
localcuts classes(19d)... 7684 nodes 12404 edges
localcuts done in 1.59 seconds
Found 17 localcuts in 1.59 seconds
Add 17 cuts (Total 9072), LP: 142337734.610368 (16.87 seconds)
localcuts classes(20d)... 7637 nodes 12331 edges
localcuts done in 1.01 seconds
Found 25 localcuts in 1.01 seconds
Add 25 cuts (Total 9097), LP: 142337734.610368 (15.58 seconds)
localcuts spheres(6d/8d)... 7706 nodes 12435 edges
localcuts done in 0.33 seconds
Found 14 localcuts in 0.33 seconds
Add 14 cuts (Total 9111), LP: 142337734.610368 (9.95 seconds)
localcuts spheres(7d/9d)... 7671 nodes 12383 edges
localcuts done in 0.35 seconds
Found 15 localcuts in 0.35 seconds
Add 15 cuts (Total 9126), LP: 142337734.610368 (12.93 seconds)
localcuts spheres(8d/10d)... 7686 nodes 12417 edges
localcuts done in 0.37 seconds
Found 20 localcuts in 0.37 seconds
Add 20 cuts (Total 9146), LP: 142337734.610368 (15.75 seconds)
localcuts spheres(9d/11d)... 7683 nodes 12407 edges
localcuts done in 0.38 seconds
Found 17 localcuts in 0.38 seconds
Add 17 cuts (Total 9163), LP: 142337734.610368 (14.90 seconds)
localcuts spheres(10d/12d)... 7728 nodes 12481 edges
localcuts done in 0.45 seconds
Found 18 localcuts in 0.45 seconds
Add 18 cuts (Total 9181), LP: 142337734.610368 (11.05 seconds)
localcuts spheres(11d/13d)... 7686 nodes 12414 edges
localcuts done in 0.49 seconds
Found 25 localcuts in 0.49 seconds
Add 25 cuts (Total 9206), LP: 142337734.610368 (14.75 seconds)
localcuts spheres(12d/14d)... 7680 nodes 12403 edges
localcuts done in 0.49 seconds
Found 25 localcuts in 0.49 seconds
Add 25 cuts (Total 9231), LP: 142337734.610368 (14.33 seconds)
localcuts spheres(13d/15d)... 7745 nodes 12512 edges
localcuts done in 1.06 seconds
Found 76 localcuts in 1.06 seconds
Add 76 cuts (Total 9307), LP: 142337734.610368 (18.15 seconds)
localcuts spheres(14d/16d)... 7826 nodes 12622 edges
localcuts done in 0.76 seconds
Found 68 localcuts in 0.76 seconds
Add 68 cuts (Total 9375), LP: 142337734.610368 (20.00 seconds)
localcuts spheres(15d/17d)... 7728 nodes 12499 edges
localcuts done in 1.33 seconds
Found 83 localcuts in 1.33 seconds
Add 83 cuts (Total 9458), LP: 142337734.610368 (30.80 seconds)
localcuts spheres(16d/18d)... 7770 nodes 12551 edges
localcuts done in 3.26 seconds
Found 63 localcuts in 3.26 seconds
Add 63 cuts (Total 9521), LP: 142337734.610368 (31.95 seconds)
localcuts spheres(17d/19d)... 7530 nodes 12223 edges
localcuts done in 0.90 seconds
Found 28 localcuts in 0.90 seconds
Add 28 cuts (Total 9549), LP: 142337734.610368 (7.13 seconds)
localcuts spheres(18d/20d)... 7598 nodes 12315 edges
localcuts done in 1.32 seconds
Found 15 localcuts in 1.32 seconds
Add 15 cuts (Total 9564), LP: 142337734.610368 (3.79 seconds)
CCtsp_generate_edges (277700)
Time for Add edges: 2.78 seconds (402.75 total in 11 calls)
(SPARSE) 0 edges added, penalty -0.000000, val 142337734.610368
Time for Sparse edge check: 2.80 seconds (343.00 total in 9 calls)
Write Pool: 196101 cuts
Write Domino Pool: 3108 cuts
Time for Cutting inside loop: 3099.87 seconds (22974.99 total in 9 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
Time for Add edges: 13.45 seconds (416.20 total in 12 calls)
0 edges added, penalty -0.000000
New lower bound: 142337734.610368
Time for Full edge check: 13.48 seconds (73.41 total in 3 calls)
Setting tolerances: next cuts 459.6939 next round 45.9694
LP has: 95464 rows 169106 columns 1029301 nonzeros
Loading lp...done in 1.03 seconds
LP has: 95464 rows 169106 columns 1029301 nonzeros
Found 329 pool cuts (max viol 2.9920) in 1.04 seconds
Add 267 cuts (Total 9065), LP: 142337735.460193 (98.39 seconds)
Found 314 pool cuts (max viol 2.0000) in 1.03 seconds
Add 250 cuts (Total 8816), LP: 142337736.222240 (25.82 seconds)
Found 85 pool cuts (max viol 2.0000) in 1.03 seconds
Add 72 cuts (Total 8888), LP: 142337736.222240 (13.13 seconds)
Found 37 pool cuts (max viol 0.1758) in 1.03 seconds
Add 24 cuts (Total 8912), LP: 142337736.222240 (2.35 seconds)
Found 20 pool cuts (max viol 0.1229) in 1.05 seconds
Add 7 cuts (Total 8919), LP: 142337736.222240 (2.24 seconds)
Found 14 pool cuts (max viol 0.0427) in 1.04 seconds
Add 1 cuts (Total 8920), LP: 142337736.222240 (1.27 seconds)
Found 13 pool cuts (max viol 0.0020) in 1.02 seconds
Add 0 cuts (Total 8920), LP: 142337736.222240 (0.02 seconds)
Found 14 connect cuts in 0.02 seconds
Add 14 cuts (Total 8934), LP: 142337736.222240 (1.30 seconds)
Found 40 segment cuts in 0.13 seconds
Add 19 cuts (Total 8953), LP: 142337736.222240 (7.52 seconds)
Found 50 fast blossoms in 0.08 seconds
Add 50 cuts (Total 9003), LP: 142337736.222240 (31.14 seconds)
Found 42 Groetschel-Holland blossoms in 0.07 seconds
Add 36 cuts (Total 9039), LP: 142337736.222240 (26.74 seconds)
Block Combs
Type 0: 253 cuts 1.4530 max violation 0.75 seconds
Type 1: 171 cuts 1.4530 max violation 0.73 seconds
Type 2: 135 cuts 1.6150 max violation 0.50 seconds
Type 4: 122 cuts 1.6295 max violation 0.52 seconds
Type 5: 16 cuts 1.2695 max violation 2.42 seconds
Olaf 1: 105 cuts 1.3667 max violation 1.01 seconds
Olaf 2: 98 cuts 1.3667 max violation 1.18 seconds
Olaf 3: 88 cuts 2.0000 max violation 0.97 seconds
Olaf 4: 87 cuts 2.0000 max violation 1.03 seconds
Total Time in block_combs: 9.76
Found 1075 block combs in 9.76 seconds
Add 661 cuts (Total 9700), LP: 142337736.222240 (96.81 seconds)
Found 5 exact subtours in 0.03 seconds
Add 5 cuts (Total 9705), LP: 142337736.222240 (3.38 seconds)
Add 27 cuts (Total 9732), LP: 142337736.222240 (10.72 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 9734), LP: 142337736.222240 (1.21 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 9735), LP: 142337736.222240 (1.26 seconds)
Found 480 exact subtours in 0.86 seconds
Add 303 cuts (Total 10038), LP: 142337736.222240 (94.89 seconds)
Found 350 exact subtours in 0.78 seconds
Add 220 cuts (Total 10258), LP: 142337736.222240 (32.12 seconds)
Found 200 exact subtours in 0.78 seconds
Add 61 cuts (Total 10319), LP: 142337736.222240 (14.94 seconds)
Found 185 exact subtours in 0.73 seconds
Add 47 cuts (Total 10366), LP: 142337736.222240 (13.94 seconds)
Found 157 exact subtours in 0.74 seconds
Add 18 cuts (Total 10384), LP: 142337736.222240 (4.58 seconds)
Found 143 exact subtours in 0.63 seconds
Add 4 cuts (Total 10388), LP: 142337736.222240 (2.53 seconds)
Found 149 exact subtours in 0.65 seconds
Add 10 cuts (Total 10398), LP: 142337736.222240 (3.10 seconds)
Found 148 exact subtours in 0.66 seconds
Add 6 cuts (Total 10404), LP: 142337736.222240 (2.08 seconds)
Found 146 exact subtours in 0.65 seconds
Add 4 cuts (Total 10408), LP: 142337736.222240 (1.40 seconds)
Found 144 exact subtours in 0.66 seconds
Add 1 cuts (Total 10409), LP: 142337736.222240 (1.59 seconds)
Found 144 exact subtours in 0.67 seconds
Add 1 cuts (Total 10410), LP: 142337736.222240 (2.35 seconds)
Found 143 exact subtours in 0.66 seconds
Add 0 cuts (Total 10410), LP: 142337736.222240 (0.02 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 7496, Ecount = 12259
Shrunk ecount = 11861, ncount = 7291
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 7291 nodes, and 11861 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 7291 nodes, and 11861 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 5 trivial dominos
GetDual: graph still has 96 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 1
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 4572 nodes and 23696 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 9
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 17800 dominoes.
Done.
DP Separator: Found 17805 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 964.640000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2558 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (3551 combs) ...
Found 5000 domino cuts in 1219.57 seconds
Add 1772 cuts (Total 12182), LP: 142337736.222240 (621.96 seconds)
Added 1772 shrunk domino cuts
Found 500 tighten_lp cuts (max viol 1.0000) in 16.37 seconds
Add 478 cuts (Total 9868), LP: 142337736.484325 (297.02 seconds)
Found 35 CLOSE tighten_lp cuts (max viol 0.5000) in 1.96 seconds
Add 35 cuts (Total 9589), LP: 142337736.656530 (110.57 seconds)
Found 500 double deckers (max viol 4.3884) in 12.37 seconds
Add 464 cuts (Total 8876), LP: 142337737.391709 (333.78 seconds)
Found 30 CLOSE double deckers (max viol 0.1530) in 2.32 seconds
Add 30 cuts (Total 8906), LP: 142337737.391709 (4.54 seconds)
Found 478 consecutive ones cuts in 264.99 seconds
Add 356 cuts (Total 9030), LP: 142337737.599765 (175.83 seconds)
localcuts spheres(6d/8d)... 7718 nodes 12358 edges
localcuts done in 0.33 seconds
Found 45 localcuts in 0.33 seconds
Add 45 cuts (Total 9075), LP: 142337737.599765 (20.59 seconds)
localcuts spheres(7d/9d)... 7805 nodes 12484 edges
localcuts done in 0.38 seconds
Found 48 localcuts in 0.38 seconds
Add 48 cuts (Total 9123), LP: 142337737.599765 (27.09 seconds)
localcuts spheres(8d/10d)... 7937 nodes 12690 edges
localcuts done in 0.40 seconds
Found 29 localcuts in 0.40 seconds
Add 29 cuts (Total 9152), LP: 142337737.599765 (30.32 seconds)
localcuts spheres(9d/11d)... 8022 nodes 12818 edges
localcuts done in 0.47 seconds
Found 49 localcuts in 0.47 seconds
Add 49 cuts (Total 9201), LP: 142337737.599765 (16.46 seconds)
localcuts spheres(10d/12d)... 8004 nodes 12779 edges
localcuts done in 0.59 seconds
Found 44 localcuts in 0.59 seconds
Add 44 cuts (Total 9245), LP: 142337737.599765 (20.51 seconds)
localcuts spheres(11d/13d)... 7839 nodes 12538 edges
localcuts done in 1.56 seconds
Found 39 localcuts in 1.56 seconds
Add 39 cuts (Total 9284), LP: 142337737.599765 (19.73 seconds)
localcuts spheres(12d/14d)... 7978 nodes 12744 edges
localcuts done in 0.63 seconds
Found 34 localcuts in 0.63 seconds
Add 34 cuts (Total 9318), LP: 142337737.599765 (4.70 seconds)
localcuts spheres(13d/15d)... 7915 nodes 12649 edges
localcuts done in 0.65 seconds
Found 20 localcuts in 0.65 seconds
Add 20 cuts (Total 9338), LP: 142337737.599765 (11.74 seconds)
localcuts spheres(14d/16d)... 7893 nodes 12613 edges
localcuts done in 0.73 seconds
Found 12 localcuts in 0.73 seconds
Add 12 cuts (Total 9350), LP: 142337737.599765 (12.39 seconds)
localcuts spheres(15d/17d)... 7877 nodes 12583 edges
localcuts done in 0.91 seconds
Found 32 localcuts in 0.91 seconds
Add 32 cuts (Total 9382), LP: 142337737.599765 (14.97 seconds)
localcuts spheres(16d/18d)... 7880 nodes 12578 edges
localcuts done in 1.77 seconds
Found 59 localcuts in 1.77 seconds
Add 59 cuts (Total 9441), LP: 142337737.599765 (18.00 seconds)
localcuts spheres(17d/19d)... 7991 nodes 12752 edges
localcuts done in 2.24 seconds
Found 75 localcuts in 2.24 seconds
Add 75 cuts (Total 9516), LP: 142337737.599765 (48.73 seconds)
localcuts spheres(18d/20d)... 7860 nodes 12565 edges
localcuts done in 2.46 seconds
Found 56 localcuts in 2.46 seconds
Add 56 cuts (Total 9572), LP: 142337737.599765 (35.83 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.36 seconds (295.91 total in 15 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 7.64 seconds (423.84 total in 13 calls)
(SPARSE) 7 edges added, penalty -0.000000, val 142337737.599765
Time for Sparse edge check: 7.65 seconds (350.65 total in 10 calls)
Write Pool: 197286 cuts
Write Domino Pool: 3510 cuts
Time for Cutting inside loop: 3966.33 seconds (26941.32 total in 10 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 13.70 seconds (437.54 total in 14 calls)
0 edges added, penalty -0.000000
New lower bound: 142337737.599765
Time for Full edge check: 13.74 seconds (87.15 total in 4 calls)
Time for Cutting Loop: 7097.21 seconds (27036.19 total in 2 calls)
Number of outside rounds: 2
SETTING MAXCHUNKSIZE = 24
Setting tolerances: next cuts 459.6640 next round 45.9664
CCtsp_init_edgegenerator (50)
..................................................................................... 2361755 edges
LP has: 95472 rows 169113 columns 1058620 nonzeros
Loading lp...done in 1.09 seconds
LP has: 95472 rows 169113 columns 1058650 nonzeros
Found 500 pool cuts (max viol 3.9944) in 1.06 seconds
Add 408 cuts (Total 9980), LP: 142337737.599765 (106.41 seconds)
Found 433 pool cuts (max viol 1.5118) in 1.03 seconds
Add 285 cuts (Total 8694), LP: 142337737.616749 (65.39 seconds)
Found 312 pool cuts (max viol 2.1000) in 1.04 seconds
Add 236 cuts (Total 8792), LP: 142337737.631066 (43.56 seconds)
Found 191 pool cuts (max viol 1.0717) in 1.04 seconds
Add 158 cuts (Total 8763), LP: 142337737.631956 (21.04 seconds)
Found 148 pool cuts (max viol 1.9450) in 1.05 seconds
Add 118 cuts (Total 8881), LP: 142337737.631956 (9.87 seconds)
Found 53 pool cuts (max viol 0.6237) in 1.05 seconds
Add 33 cuts (Total 8914), LP: 142337737.631956 (5.23 seconds)
Found 23 pool cuts (max viol 0.0712) in 1.05 seconds
Add 3 cuts (Total 8917), LP: 142337737.631956 (1.58 seconds)
Found 27 pool cuts (max viol 0.0268) in 1.07 seconds
Add 7 cuts (Total 8924), LP: 142337737.631956 (1.65 seconds)
Found 23 pool cuts (max viol 0.0268) in 1.05 seconds
Add 3 cuts (Total 8927), LP: 142337737.631956 (2.09 seconds)
Found 20 pool cuts (max viol 0.0018) in 1.04 seconds
Add 0 cuts (Total 8927), LP: 142337737.631956 (0.03 seconds)
Found 34 connect cuts in 0.02 seconds
Add 34 cuts (Total 8961), LP: 142337737.631956 (19.89 seconds)
Found 86 segment cuts in 0.12 seconds
Add 53 cuts (Total 9014), LP: 142337737.631956 (18.49 seconds)
Found 54 fast blossoms in 0.09 seconds
Add 54 cuts (Total 9068), LP: 142337737.631956 (53.07 seconds)
Found 42 Groetschel-Holland blossoms in 0.09 seconds
Add 41 cuts (Total 9109), LP: 142337737.631956 (26.03 seconds)
Block Combs
Type 0: 290 cuts 1.8445 max violation 0.77 seconds
Type 1: 188 cuts 1.8445 max violation 0.77 seconds
Type 2: 180 cuts 1.6365 max violation 0.65 seconds
Type 4: 127 cuts 1.5652 max violation 0.56 seconds
Type 5: 25 cuts 0.8182 max violation 1.33 seconds
Olaf 1: 121 cuts 1.7001 max violation 1.04 seconds
Olaf 2: 122 cuts 1.5652 max violation 1.05 seconds
Olaf 3: 131 cuts 1.9999 max violation 0.90 seconds
Olaf 4: 167 cuts 1.9999 max violation 0.88 seconds
Total Time in block_combs: 8.58
Found 1351 block combs in 8.58 seconds
Add 790 cuts (Total 9899), LP: 142337737.631956 (193.57 seconds)
Found 8 exact subtours in 0.03 seconds
Add 8 cuts (Total 9907), LP: 142337737.631956 (5.90 seconds)
Add 27 cuts (Total 9934), LP: 142337737.631956 (20.00 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 9935), LP: 142337737.631956 (1.23 seconds)
Found 681 exact subtours in 1.06 seconds
Add 421 cuts (Total 8264), LP: 142337737.685487 (213.27 seconds)
Found 40 exact subtours in 0.03 seconds
Add 40 cuts (Total 8304), LP: 142337737.685487 (2.15 seconds)
Found 8 exact subtours in 0.02 seconds
Add 8 cuts (Total 8312), LP: 142337737.685487 (1.37 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8313), LP: 142337737.685487 (1.11 seconds)
Found 534 exact subtours in 0.74 seconds
Add 339 cuts (Total 8652), LP: 142337737.685487 (35.31 seconds)
Found 357 exact subtours in 0.71 seconds
Add 208 cuts (Total 8860), LP: 142337737.685487 (22.16 seconds)
Found 222 exact subtours in 0.65 seconds
Add 67 cuts (Total 8927), LP: 142337737.685487 (12.93 seconds)
Found 201 exact subtours in 0.65 seconds
Add 61 cuts (Total 8988), LP: 142337737.685487 (12.33 seconds)
Found 157 exact subtours in 0.59 seconds
Add 20 cuts (Total 9008), LP: 142337737.685487 (5.61 seconds)
Found 167 exact subtours in 0.56 seconds
Add 26 cuts (Total 9034), LP: 142337737.685487 (2.16 seconds)
Found 149 exact subtours in 0.48 seconds
Add 11 cuts (Total 9045), LP: 142337737.685487 (2.16 seconds)
Found 146 exact subtours in 0.63 seconds
Add 2 cuts (Total 9047), LP: 142337737.685487 (1.42 seconds)
Found 143 exact subtours in 0.60 seconds
Add 4 cuts (Total 9051), LP: 142337737.685487 (1.70 seconds)
Found 141 exact subtours in 0.60 seconds
Add 0 cuts (Total 9051), LP: 142337737.685487 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 7319, Ecount = 11911
Shrunk ecount = 11583, ncount = 7172
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 7172 nodes, and 11583 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 7172 nodes, and 11583 edges.
DP Separator: Graph G^* is planar.
Saving graph (binary format) to file graph.planar.b.x ... done.
DP Separator: Computing dual of G^*.
GetDual: found 5 trivial dominos
GetDual: graph still has 92 extra paralel edges
GetDual: Not One Eliminated edges: 1
GetDual: Number of loops edges: 3
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 4413 nodes and 23144 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 10
WARNING: assuming contiguous and unique ID for nodes, in EGsendRealGraph (lib/eg_util.c:282)
Graph sent. Waiting for dominoes.
Preparing to receive dominoes.
Receiving 17413 dominoes.
Done.
DP Separator: Found 17418 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 980.760000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2600 / 5000 are maximally violated.
DP Separator: Violation Frequency:
[0.450000, 0.500000] 5000
DP Separator: Finished finding cuts.
DP Separator: Found 5000 primal DP-Constraints.
DP Separator: Bye.
BACK from DPseparator
Found 5000 shunk domino cuts (3303 combs) ...
Found 5000 domino cuts in 1254.48 seconds
Add 1643 cuts (Total 8535), LP: 142337739.124294 (282.71 seconds)
Added 1643 shrunk domino cuts
Found 420 tighten_lp cuts (max viol 1.0000) in 16.63 seconds
Add 356 cuts (Total 8275), LP: 142337741.751942 (123.48 seconds)
Found 37 CLOSE tighten_lp cuts (max viol 0.4310) in 2.10 seconds
Add 37 cuts (Total 8180), LP: 142337744.399377 (45.59 seconds)
Found 418 double deckers (max viol 4.0000) in 14.63 seconds
Add 363 cuts (Total 8356), LP: 142337744.568317 (149.49 seconds)
Found 5 CLOSE double deckers (max viol 0.0287) in 2.07 seconds
Add 5 cuts (Total 8361), LP: 142337744.568317 (2.44 seconds)
Found 551 consecutive ones cuts in 250.76 seconds
Add 412 cuts (Total 7076), LP: 142337746.546401 (184.60 seconds)
localcuts classes(8d)... 5958 nodes 9467 edges
localcuts done in 0.17 seconds
Found 25 localcuts in 0.17 seconds
Add 25 cuts (Total 7101), LP: 142337746.546401 (5.77 seconds)
localcuts classes(9d)... 6195 nodes 9811 edges
localcuts done in 0.20 seconds
Found 31 localcuts in 0.20 seconds
Add 31 cuts (Total 7132), LP: 142337746.546401 (23.42 seconds)
localcuts classes(10d)... 6123 nodes 9731 edges
localcuts done in 0.22 seconds
Found 32 localcuts in 0.22 seconds
Add 32 cuts (Total 7164), LP: 142337746.546401 (9.14 seconds)
localcuts classes(11d)... 6313 nodes 9993 edges
localcuts done in 0.24 seconds
Found 34 localcuts in 0.24 seconds
Add 34 cuts (Total 7198), LP: 142337746.546401 (15.06 seconds)
localcuts classes(12d)... 6251 nodes 9884 edges
localcuts done in 0.24 seconds
Found 32 localcuts in 0.24 seconds
Add 32 cuts (Total 7230), LP: 142337746.546401 (12.03 seconds)
localcuts classes(13d)... 6371 nodes 10053 edges
localcuts done in 0.28 seconds
Found 28 localcuts in 0.28 seconds
Add 28 cuts (Total 7258), LP: 142337746.546401 (5.62 seconds)
localcuts classes(14d)... 6408 nodes 10121 edges
localcuts done in 0.23 seconds
Found 25 localcuts in 0.23 seconds
Add 25 cuts (Total 7283), LP: 142337746.546401 (14.15 seconds)
localcuts classes(15d)... 6436 nodes 10187 edges
localcuts done in 0.31 seconds
Found 23 localcuts in 0.31 seconds
Add 23 cuts (Total 7306), LP: 142337746.546401 (6.15 seconds)
localcuts classes(16d)... 6530 nodes 10329 edges
localcuts done in 0.26 seconds
Found 22 localcuts in 0.26 seconds
Add 22 cuts (Total 7328), LP: 142337746.546401 (9.22 seconds)
localcuts classes(17d)... 6748 nodes 10664 edges
localcuts done in 0.30 seconds
Found 19 localcuts in 0.30 seconds
Add 19 cuts (Total 7347), LP: 142337746.546401 (5.18 seconds)
localcuts classes(18d)... 6751 nodes 10648 edges
localcuts done in 0.32 seconds
Found 15 localcuts in 0.32 seconds
Add 15 cuts (Total 7362), LP: 142337746.546401 (16.79 seconds)
localcuts classes(19d)... 6580 nodes 10404 edges
localcuts done in 0.28 seconds
Found 10 localcuts in 0.28 seconds
Add 10 cuts (Total 7372), LP: 142337746.546401 (1.81 seconds)
localcuts classes(20d)... 6585 nodes 10418 edges
localcuts done in 0.27 seconds
Found 7 localcuts in 0.27 seconds
Add 7 cuts (Total 7379), LP: 142337746.546401 (1.66 seconds)
localcuts classes(21d)... 6599 nodes 10440 edges
localcuts done in 1.58 seconds
Found 10 localcuts in 1.58 seconds
Add 10 cuts (Total 7389), LP: 142337746.546401 (2.24 seconds)
localcuts classes(22d)... 6559 nodes 10378 edges
localcuts done in 0.68 seconds
Found 9 localcuts in 0.68 seconds
Add 9 cuts (Total 7398), LP: 142337746.546401 (2.87 seconds)
localcuts classes(23d)... 6601 nodes 10453 edges
localcuts done in 1.11 seconds
Found 10 localcuts in 1.11 seconds
Add 10 cuts (Total 7408), LP: 142337746.546401 (2.40 seconds)
localcuts classes(24d)... 6620 nodes 10482 edges
localcuts done in 3.43 seconds
Found 8 localcuts in 3.43 seconds
Add 8 cuts (Total 7416), LP: 142337746.546401 (1.73 seconds)
localcuts spheres(6d/8d)... 6593 nodes 10444 edges
localcuts done in 0.14 seconds
Found 1 localcuts in 0.14 seconds
Add 1 cuts (Total 7417), LP: 142337746.546401 (1.22 seconds)
localcuts spheres(7d/9d)... 6590 nodes 10439 edges
localcuts done in 0.14 seconds
localcuts spheres(8d/10d)... 6590 nodes 10439 edges
localcuts done in 0.14 seconds
Found 1 localcuts in 0.14 seconds
Add 1 cuts (Total 7418), LP: 142337746.546401 (1.10 seconds)
localcuts spheres(9d/11d)... 6590 nodes 10439 edges
localcuts done in 0.15 seconds
Found 2 localcuts in 0.15 seconds
Add 2 cuts (Total 7420), LP: 142337746.546401 (1.81 seconds)
localcuts spheres(10d/12d)... 6589 nodes 10443 edges
localcuts done in 0.15 seconds
localcuts spheres(11d/13d)... 6589 nodes 10443 edges
localcuts done in 0.17 seconds
Found 1 localcuts in 0.17 seconds
Add 1 cuts (Total 7421), LP: 142337746.546401 (1.13 seconds)
localcuts spheres(12d/14d)... 6607 nodes 10472 edges
localcuts done in 0.19 seconds
Found 2 localcuts in 0.19 seconds
Add 2 cuts (Total 7423), LP: 142337746.546401 (1.83 seconds)
localcuts spheres(13d/15d)... 6603 nodes 10455 edges
localcuts done in 0.16 seconds
Found 2 localcuts in 0.16 seconds
Add 2 cuts (Total 7425), LP: 142337746.546401 (1.39 seconds)
localcuts spheres(14d/16d)... 6605 nodes 10459 edges
localcuts done in 0.20 seconds
Found 5 localcuts in 0.20 seconds
Add 5 cuts (Total 7430), LP: 142337746.546401 (6.16 seconds)
localcuts spheres(15d/17d)... 6708 nodes 10588 edges
localcuts done in 0.16 seconds
Found 3 localcuts in 0.16 seconds
Add 3 cuts (Total 7433), LP: 142337746.546401 (9.55 seconds)
localcuts spheres(16d/18d)... 6739 nodes 10638 edges
localcuts done in 1.01 seconds
Found 7 localcuts in 1.01 seconds
Add 7 cuts (Total 7440), LP: 142337746.546401 (2.51 seconds)
localcuts spheres(17d/19d)... 6742 nodes 10646 edges
localcuts done in 0.24 seconds
Found 4 localcuts in 0.24 seconds
Add 4 cuts (Total 7444), LP: 142337746.546401 (2.29 seconds)
localcuts spheres(18d/20d)... 6777 nodes 10696 edges
localcuts done in 0.30 seconds