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
Found 5 localcuts in 0.30 seconds
Add 5 cuts (Total 7449), LP: 142337746.546401 (2.51 seconds)
localcuts spheres(19d/21d)... 6760 nodes 10657 edges
localcuts done in 1.46 seconds
Found 30 localcuts in 1.46 seconds
Add 30 cuts (Total 7479), LP: 142337746.546401 (12.44 seconds)
localcuts spheres(20d/22d)... 6672 nodes 10535 edges
localcuts done in 2.67 seconds
Found 35 localcuts in 2.67 seconds
Add 35 cuts (Total 7514), LP: 142337746.546401 (7.12 seconds)
localcuts spheres(21d/23d)... 6738 nodes 10632 edges
localcuts done in 1.91 seconds
Found 9 localcuts in 1.91 seconds
Add 9 cuts (Total 7523), LP: 142337746.546401 (3.02 seconds)
localcuts spheres(22d/24d)... 6750 nodes 10650 edges
localcuts done in 8.35 seconds
Found 63 localcuts in 8.35 seconds
Add 63 cuts (Total 7586), LP: 142337746.546401 (26.16 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 3.91 seconds (299.82 total in 16 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 9.37 seconds (446.91 total in 15 calls)
(SPARSE) 1 edges added, penalty -0.000000, val 142337746.232970
Time for Sparse edge check: 9.39 seconds (360.04 total in 11 calls)
Write Pool: 198294 cuts
Write Domino Pool: 3920 cuts
Time for Cutting inside loop: 3606.07 seconds (30547.39 total in 11 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 12.91 seconds (459.82 total in 16 calls)
0 edges added, penalty -0.000000
New lower bound: 142337746.232970
Time for Full edge check: 12.94 seconds (100.09 total in 5 calls)
Setting tolerances: next cuts 459.5777 next round 45.9578
LP has: 93486 rows 169114 columns 945927 nonzeros
Loading lp...done in 0.91 seconds
LP has: 93486 rows 169114 columns 945924 nonzeros
Found 500 pool cuts (max viol 4.0000) in 1.07 seconds
Add 441 cuts (Total 8027), LP: 142337746.232970 (40.84 seconds)
Found 500 pool cuts (max viol 1.6000) in 1.04 seconds
Add 367 cuts (Total 7642), LP: 142337746.859162 (32.32 seconds)
Found 500 pool cuts (max viol 1.0000) in 1.04 seconds
Add 301 cuts (Total 7650), LP: 142337748.100792 (53.41 seconds)
Found 204 pool cuts (max viol 1.5000) in 1.04 seconds
Add 140 cuts (Total 7544), LP: 142337748.278093 (10.88 seconds)
Found 175 pool cuts (max viol 1.4737) in 1.03 seconds
Add 103 cuts (Total 7536), LP: 142337748.309503 (7.36 seconds)
Found 97 pool cuts (max viol 0.6667) in 1.01 seconds
Add 52 cuts (Total 7588), LP: 142337748.309503 (2.57 seconds)
Found 64 pool cuts (max viol 0.4992) in 1.04 seconds
Add 18 cuts (Total 7606), LP: 142337748.309503 (1.50 seconds)
Found 48 pool cuts (max viol 0.0345) in 1.02 seconds
Add 3 cuts (Total 7609), LP: 142337748.309503 (1.25 seconds)
Found 45 pool cuts (max viol 0.0020) in 1.03 seconds
Add 0 cuts (Total 7609), LP: 142337748.309503 (0.02 seconds)
Found 73 connect cuts in 0.02 seconds
Add 73 cuts (Total 7682), LP: 142337748.309503 (2.96 seconds)
Found 83 segment cuts in 0.11 seconds
Add 43 cuts (Total 7725), LP: 142337748.309503 (3.72 seconds)
Found 60 fast blossoms in 0.10 seconds
Add 60 cuts (Total 7785), LP: 142337748.309503 (7.14 seconds)
Found 60 Groetschel-Holland blossoms in 0.08 seconds
Add 55 cuts (Total 7840), LP: 142337748.309503 (5.81 seconds)
Block Combs
Type 0: 286 cuts 1.9998 max violation 0.76 seconds
Type 1: 193 cuts 1.9999 max violation 0.73 seconds
Type 2: 160 cuts 1.8645 max violation 0.56 seconds
Type 4: 129 cuts 1.8645 max violation 0.47 seconds
Type 5: 12 cuts 0.6657 max violation 1.31 seconds
Olaf 1: 119 cuts 2.0000 max violation 1.09 seconds
Olaf 2: 154 cuts 1.9998 max violation 1.08 seconds
Olaf 3: 106 cuts 2.0000 max violation 1.09 seconds
Olaf 4: 162 cuts 2.0000 max violation 0.99 seconds
Total Time in block_combs: 8.76
Found 1321 block combs in 8.76 seconds
Add 790 cuts (Total 7763), LP: 142337755.208954 (71.05 seconds)
Found 48 exact subtours in 0.04 seconds
Add 48 cuts (Total 7811), LP: 142337755.208954 (2.54 seconds)
Add 56 cuts (Total 7867), LP: 142337755.208954 (4.34 seconds)
Found 17 exact subtours in 0.02 seconds
Add 17 cuts (Total 7884), LP: 142337755.208954 (2.13 seconds)
Found 4 exact subtours in 0.03 seconds
Add 4 cuts (Total 7888), LP: 142337755.208954 (1.10 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7890), LP: 142337755.208954 (1.04 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7891), LP: 142337755.208954 (1.08 seconds)
Found 737 exact subtours in 0.64 seconds
Add 484 cuts (Total 8375), LP: 142337755.208954 (39.10 seconds)
Found 5 exact subtours in 0.02 seconds
Add 5 cuts (Total 8380), LP: 142337755.208954 (1.17 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8381), LP: 142337755.208954 (1.17 seconds)
Found 454 exact subtours in 0.56 seconds
Add 252 cuts (Total 8633), LP: 142337755.208954 (16.32 seconds)
Found 302 exact subtours in 0.62 seconds
Add 97 cuts (Total 8730), LP: 142337755.208954 (9.14 seconds)
Found 251 exact subtours in 0.63 seconds
Add 56 cuts (Total 8786), LP: 142337755.208954 (6.49 seconds)
Found 227 exact subtours in 0.64 seconds
Add 32 cuts (Total 8818), LP: 142337755.208954 (2.79 seconds)
Found 202 exact subtours in 0.62 seconds
Add 6 cuts (Total 8824), LP: 142337755.208954 (3.08 seconds)
Found 200 exact subtours in 0.59 seconds
Add 4 cuts (Total 8828), LP: 142337755.208954 (1.37 seconds)
Found 198 exact subtours in 0.59 seconds
Add 2 cuts (Total 8830), LP: 142337755.208954 (1.25 seconds)
Found 201 exact subtours in 0.59 seconds
Add 5 cuts (Total 8835), LP: 142337755.208954 (1.20 seconds)
Found 196 exact subtours in 0.62 seconds
Add 0 cuts (Total 8835), LP: 142337755.208954 (0.02 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 7148, Ecount = 11676
Shrunk ecount = 11337, ncount = 7004
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 7004 nodes, and 11337 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 7004 nodes, and 11337 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 84 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 4335 nodes and 22650 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 11
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 17300 dominoes.
Done.
DP Separator: Found 17305 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 1002.400000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 3140 / 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 (3684 combs) ...
Found 5000 domino cuts in 1271.35 seconds
Add 1279 cuts (Total 10114), LP: 142337755.208954 (215.17 seconds)
Added 1279 shrunk domino cuts
Found 387 tighten_lp cuts (max viol 1.0000) in 15.24 seconds
Add 337 cuts (Total 8301), LP: 142337757.772177 (170.93 seconds)
Found 42 CLOSE tighten_lp cuts (max viol 1.0000) in 1.91 seconds
Add 42 cuts (Total 8241), LP: 142337759.076938 (40.40 seconds)
Found 412 double deckers (max viol 4.0000) in 15.41 seconds
Add 348 cuts (Total 8307), LP: 142337759.407576 (118.55 seconds)
Found 9 CLOSE double deckers (max viol 1.0000) in 2.14 seconds
Add 9 cuts (Total 8248), LP: 142337759.439406 (13.83 seconds)
Found 1019 consecutive ones cuts in 514.15 seconds
Add 519 cuts (Total 7837), LP: 142337777.326766 (139.20 seconds)
localcuts spheres(6d/8d)... 7394 nodes 11813 edges
localcuts done in 0.12 seconds
localcuts spheres(7d/9d)... 7394 nodes 11813 edges
localcuts done in 0.11 seconds
localcuts spheres(8d/10d)... 7394 nodes 11813 edges
localcuts done in 0.12 seconds
localcuts spheres(9d/11d)... 7394 nodes 11813 edges
localcuts done in 0.11 seconds
localcuts spheres(10d/12d)... 7394 nodes 11813 edges
localcuts done in 0.12 seconds
localcuts spheres(11d/13d)... 7394 nodes 11813 edges
localcuts done in 0.12 seconds
localcuts spheres(12d/14d)... 7394 nodes 11813 edges
localcuts done in 0.13 seconds
localcuts spheres(13d/15d)... 7394 nodes 11813 edges
localcuts done in 0.11 seconds
localcuts spheres(14d/16d)... 7394 nodes 11813 edges
localcuts done in 0.13 seconds
localcuts spheres(15d/17d)... 7394 nodes 11813 edges
localcuts done in 0.14 seconds
localcuts spheres(16d/18d)... 7394 nodes 11813 edges
localcuts done in 0.13 seconds
localcuts spheres(17d/19d)... 7394 nodes 11813 edges
localcuts done in 0.12 seconds
localcuts spheres(18d/20d)... 7394 nodes 11813 edges
localcuts done in 0.14 seconds
localcuts spheres(19d/21d)... 7394 nodes 11813 edges
localcuts done in 0.14 seconds
localcuts spheres(20d/22d)... 7394 nodes 11813 edges
localcuts done in 0.13 seconds
localcuts spheres(21d/23d)... 7394 nodes 11813 edges
localcuts done in 0.13 seconds
localcuts spheres(22d/24d)... 7394 nodes 11813 edges
localcuts done in 0.16 seconds
CCtsp_generate_edges (277700)
Time for Add edges optimize: 12.13 seconds (311.95 total in 17 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 17.80 seconds (477.62 total in 17 calls)
(SPARSE) 2 edges added, penalty -0.047290, val 142337777.082941
Time for Sparse edge check: 17.81 seconds (377.85 total in 12 calls)
Write Pool: 199539 cuts
Write Domino Pool: 4237 cuts
Time for Cutting inside loop: 2968.47 seconds (33515.86 total in 12 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.22 seconds (313.17 total in 18 calls)
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 27.63 seconds (505.25 total in 18 calls)
2 edges added, penalty -0.000000
New lower bound: 142337777.082940
Time for Full edge check: 27.64 seconds (127.73 total in 6 calls)
Time for Cutting Loop: 6619.01 seconds (33655.20 total in 3 calls)
Number of outside rounds: 2
SETTING MAXCHUNKSIZE = 28
Setting tolerances: next cuts 459.2692 next round 45.9269
CCtsp_init_edgegenerator (50)
..................................................................................... 2361750 edges
LP has: 93737 rows 169118 columns 950082 nonzeros
Loading lp...done in 0.99 seconds
LP has: 93737 rows 169118 columns 950046 nonzeros
Found 500 pool cuts (max viol 3.0000) in 1.06 seconds
Add 472 cuts (Total 8309), LP: 142337777.082941 (64.04 seconds)
Found 500 pool cuts (max viol 1.6241) in 1.04 seconds
Add 416 cuts (Total 8725), LP: 142337777.082941 (50.40 seconds)
Found 392 pool cuts (max viol 1.0005) in 1.06 seconds
Add 272 cuts (Total 7231), LP: 142337777.840381 (68.89 seconds)
Found 500 pool cuts (max viol 3.0000) in 1.07 seconds
Add 310 cuts (Total 7300), LP: 142337778.119956 (23.67 seconds)
Found 97 pool cuts (max viol 2.0000) in 1.04 seconds
Add 79 cuts (Total 7192), LP: 142337778.130502 (10.81 seconds)
Found 164 pool cuts (max viol 1.9989) in 1.08 seconds
Add 67 cuts (Total 7154), LP: 142337778.144722 (9.30 seconds)
Found 134 pool cuts (max viol 2.0000) in 1.03 seconds
Add 93 cuts (Total 7171), LP: 142337778.145227 (4.01 seconds)
Found 114 pool cuts (max viol 2.0000) in 1.04 seconds
Add 40 cuts (Total 7211), LP: 142337778.145227 (1.44 seconds)
Found 64 pool cuts (max viol 0.0018) in 1.03 seconds
Add 0 cuts (Total 7211), LP: 142337778.145227 (0.02 seconds)
Found 73 connect cuts in 0.04 seconds
Add 73 cuts (Total 7284), LP: 142337778.145227 (3.26 seconds)
Found 69 segment cuts in 0.11 seconds
Add 41 cuts (Total 7325), LP: 142337778.145227 (2.03 seconds)
Found 62 fast blossoms in 0.10 seconds
Add 62 cuts (Total 7387), LP: 142337778.145227 (3.00 seconds)
Found 58 Groetschel-Holland blossoms in 0.10 seconds
Add 56 cuts (Total 7443), LP: 142337778.145227 (3.14 seconds)
Block Combs
Type 0: 295 cuts 2.0000 max violation 0.67 seconds
Type 1: 211 cuts 2.0000 max violation 0.73 seconds
Type 2: 180 cuts 1.9155 max violation 0.55 seconds
Type 4: 148 cuts 1.7466 max violation 0.53 seconds
Type 5: 17 cuts 1.4810 max violation 1.60 seconds
Olaf 1: 149 cuts 2.0000 max violation 0.91 seconds
Olaf 2: 169 cuts 1.9999 max violation 0.93 seconds
Olaf 3: 97 cuts 1.9831 max violation 0.80 seconds
Olaf 4: 94 cuts 1.9831 max violation 0.82 seconds
Total Time in block_combs: 8.20
Found 1360 block combs in 8.20 seconds
Add 751 cuts (Total 7498), LP: 142337780.658323 (37.61 seconds)
Found 32 exact subtours in 0.02 seconds
Add 32 cuts (Total 7530), LP: 142337780.658323 (2.16 seconds)
Add 30 cuts (Total 7560), LP: 142337780.658323 (3.43 seconds)
Found 6 exact subtours in 0.02 seconds
Add 6 cuts (Total 7566), LP: 142337780.658323 (1.72 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 7569), LP: 142337780.658323 (1.05 seconds)
Found 4 exact subtours in 0.01 seconds
Add 4 cuts (Total 7573), LP: 142337780.658323 (1.08 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 7575), LP: 142337780.658323 (1.06 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7576), LP: 142337780.658323 (1.10 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7577), LP: 142337780.658323 (1.12 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 7578), LP: 142337780.658323 (1.08 seconds)
Found 652 exact subtours in 0.64 seconds
Add 486 cuts (Total 8064), LP: 142337780.658323 (28.10 seconds)
Found 6 exact subtours in 0.02 seconds
Add 6 cuts (Total 8070), LP: 142337780.658323 (1.16 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 8072), LP: 142337780.658323 (1.12 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8073), LP: 142337780.658323 (1.14 seconds)
Found 324 exact subtours in 0.52 seconds
Add 197 cuts (Total 8270), LP: 142337780.658323 (10.06 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8271), LP: 142337780.658323 (1.13 seconds)
Found 223 exact subtours in 0.52 seconds
Add 103 cuts (Total 8374), LP: 142337780.658323 (7.22 seconds)
Found 176 exact subtours in 0.65 seconds
Add 46 cuts (Total 7532), LP: 142337780.684976 (9.67 seconds)
Found 6 exact subtours in 0.02 seconds
Add 6 cuts (Total 7538), LP: 142337780.684976 (1.14 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7539), LP: 142337780.684976 (1.59 seconds)
Found 294 exact subtours in 0.48 seconds
Add 168 cuts (Total 7590), LP: 142337780.695666 (5.11 seconds)
Found 201 exact subtours in 0.42 seconds
Add 78 cuts (Total 7668), LP: 142337780.695666 (2.76 seconds)
Found 161 exact subtours in 0.51 seconds
Add 33 cuts (Total 7701), LP: 142337780.695666 (2.63 seconds)
Found 137 exact subtours in 0.47 seconds
Add 9 cuts (Total 7710), LP: 142337780.695666 (1.58 seconds)
Found 137 exact subtours in 0.47 seconds
Add 9 cuts (Total 7719), LP: 142337780.695666 (1.23 seconds)
Found 135 exact subtours in 0.43 seconds
Add 7 cuts (Total 7726), LP: 142337780.695666 (1.23 seconds)
Found 134 exact subtours in 0.46 seconds
Add 6 cuts (Total 7732), LP: 142337780.695666 (1.41 seconds)
Found 132 exact subtours in 0.45 seconds
Add 3 cuts (Total 7735), LP: 142337780.695666 (1.26 seconds)
Found 133 exact subtours in 0.49 seconds
Add 4 cuts (Total 7739), LP: 142337780.695666 (1.48 seconds)
Found 138 exact subtours in 0.41 seconds
Add 9 cuts (Total 7748), LP: 142337780.695666 (1.53 seconds)
Found 134 exact subtours in 0.41 seconds
Add 5 cuts (Total 7753), LP: 142337780.695666 (1.48 seconds)
Found 131 exact subtours in 0.41 seconds
Add 2 cuts (Total 7755), LP: 142337780.695666 (1.11 seconds)
Found 130 exact subtours in 0.40 seconds
Add 1 cuts (Total 7756), LP: 142337780.695666 (1.12 seconds)
Found 130 exact subtours in 0.39 seconds
Add 1 cuts (Total 7757), LP: 142337780.695666 (1.28 seconds)
Found 130 exact subtours in 0.41 seconds
Add 1 cuts (Total 7758), LP: 142337780.695666 (1.11 seconds)
Found 130 exact subtours in 0.40 seconds
Add 1 cuts (Total 7759), LP: 142337780.695666 (1.19 seconds)
Found 131 exact subtours in 0.38 seconds
Add 2 cuts (Total 7761), LP: 142337780.695666 (1.49 seconds)
Found 131 exact subtours in 0.39 seconds
Add 2 cuts (Total 7763), LP: 142337780.695666 (1.12 seconds)
Found 129 exact subtours in 0.41 seconds
Add 0 cuts (Total 7763), LP: 142337780.695666 (0.01 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 6566, Ecount = 10663
Shrunk ecount = 10355, ncount = 6437
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6437 nodes, and 10355 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6437 nodes, and 10355 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 58 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 6
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3920 nodes and 20688 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 12
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 14940 dominoes.
Done.
DP Separator: Found 14944 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 950.910000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2942 / 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 (3911 combs) ...
Found 5000 domino cuts in 1178.50 seconds
Add 1484 cuts (Total 9247), LP: 142337780.695666 (256.01 seconds)
Added 1484 shrunk domino cuts
Found 232 tighten_lp cuts (max viol 1.3334) in 17.88 seconds
Add 232 cuts (Total 8065), LP: 142337781.293469 (72.94 seconds)
Found 20 CLOSE tighten_lp cuts (max viol 0.5000) in 2.04 seconds
Add 20 cuts (Total 8027), LP: 142337781.300322 (8.63 seconds)
Found 296 double deckers (max viol 3.9696) in 14.81 seconds
Add 282 cuts (Total 8079), LP: 142337781.713871 (57.49 seconds)
Found 2 CLOSE double deckers (max viol 0.4659) in 2.13 seconds
Add 2 cuts (Total 8081), LP: 142337781.713871 (1.42 seconds)
Found 698 consecutive ones cuts in 221.54 seconds
Add 518 cuts (Total 7820), LP: 142337782.726225 (88.47 seconds)
localcuts classes(8d)... 6756 nodes 10802 edges
localcuts done in 0.18 seconds
Found 20 localcuts in 0.18 seconds
Add 20 cuts (Total 7840), LP: 142337782.726225 (12.72 seconds)
localcuts classes(9d)... 6601 nodes 10593 edges
localcuts done in 0.21 seconds
Found 28 localcuts in 0.21 seconds
Add 28 cuts (Total 7868), LP: 142337782.726225 (6.49 seconds)
localcuts classes(10d)... 6749 nodes 10793 edges
localcuts done in 0.23 seconds
Found 20 localcuts in 0.23 seconds
Add 20 cuts (Total 7888), LP: 142337782.726225 (6.21 seconds)
localcuts classes(11d)... 6882 nodes 11000 edges
localcuts done in 0.24 seconds
Found 25 localcuts in 0.24 seconds
Add 25 cuts (Total 7913), LP: 142337782.726225 (10.23 seconds)
localcuts classes(12d)... 6876 nodes 11004 edges
localcuts done in 0.28 seconds
Found 24 localcuts in 0.28 seconds
Add 24 cuts (Total 7937), LP: 142337782.726225 (9.38 seconds)
localcuts classes(13d)... 6968 nodes 11163 edges
localcuts done in 0.28 seconds
Found 20 localcuts in 0.28 seconds
Add 20 cuts (Total 7957), LP: 142337782.726225 (15.91 seconds)
localcuts classes(14d)... 6887 nodes 11023 edges
localcuts done in 0.43 seconds
Found 29 localcuts in 0.43 seconds
Add 29 cuts (Total 7986), LP: 142337782.726225 (21.08 seconds)
localcuts classes(15d)... 6881 nodes 11011 edges
localcuts done in 0.35 seconds
Found 35 localcuts in 0.35 seconds
Add 35 cuts (Total 8021), LP: 142337782.726225 (16.94 seconds)
localcuts classes(16d)... 6905 nodes 11047 edges
localcuts done in 0.65 seconds
Found 33 localcuts in 0.65 seconds
Add 33 cuts (Total 8054), LP: 142337782.726225 (16.30 seconds)
localcuts classes(17d)... 7024 nodes 11226 edges
localcuts done in 0.39 seconds
Found 23 localcuts in 0.39 seconds
Add 23 cuts (Total 8077), LP: 142337782.726225 (10.93 seconds)
localcuts classes(18d)... 7193 nodes 11483 edges
localcuts done in 0.47 seconds
Found 27 localcuts in 0.47 seconds
Add 27 cuts (Total 8104), LP: 142337782.726225 (23.90 seconds)
localcuts classes(19d)... 7078 nodes 11318 edges
localcuts done in 2.73 seconds
Found 28 localcuts in 2.73 seconds
Add 28 cuts (Total 8132), LP: 142337782.726225 (15.41 seconds)
localcuts classes(20d)... 7049 nodes 11269 edges
localcuts done in 0.92 seconds
Found 23 localcuts in 0.92 seconds
Add 23 cuts (Total 8155), LP: 142337782.726225 (7.26 seconds)
localcuts classes(21d)... 7089 nodes 11337 edges
localcuts done in 2.01 seconds
Found 17 localcuts in 2.01 seconds
Add 17 cuts (Total 8172), LP: 142337782.726225 (14.62 seconds)
localcuts classes(22d)... 7083 nodes 11341 edges
localcuts done in 7.13 seconds
Found 23 localcuts in 7.13 seconds
Add 23 cuts (Total 8195), LP: 142337782.726225 (14.62 seconds)
localcuts classes(23d)... 7020 nodes 11237 edges
localcuts done in 3.55 seconds
Found 26 localcuts in 3.55 seconds
Add 26 cuts (Total 8221), LP: 142337782.726225 (16.93 seconds)
localcuts classes(24d)... 7138 nodes 11430 edges
localcuts done in 4.21 seconds
Found 33 localcuts in 4.21 seconds
Add 33 cuts (Total 8049), LP: 142337783.225132 (53.51 seconds)
localcuts classes(25d)... 7204 nodes 11502 edges
localcuts done in 2.99 seconds
Found 33 localcuts in 2.99 seconds
Add 33 cuts (Total 8082), LP: 142337783.225132 (16.85 seconds)
localcuts classes(26d)... 7245 nodes 11573 edges
---localcuts done in 12.64 seconds
Found 41 localcuts in 12.64 seconds
Add 41 cuts (Total 8123), LP: 142337783.225132 (20.41 seconds)
localcuts classes(27d)... 7329 nodes 11691 edges
----localcuts done in 22.57 seconds
Found 32 localcuts in 22.57 seconds
Add 32 cuts (Total 8155), LP: 142337783.225132 (20.88 seconds)
localcuts classes(28d)... 7316 nodes 11681 edges
------localcuts done in 35.67 seconds
Found 33 localcuts in 35.67 seconds
Add 33 cuts (Total 8188), LP: 142337783.225132 (22.58 seconds)
localcuts spheres(6d/8d)... 7422 nodes 11855 edges
localcuts done in 0.27 seconds
Found 16 localcuts in 0.27 seconds
Add 16 cuts (Total 8204), LP: 142337783.225132 (23.20 seconds)
localcuts spheres(7d/9d)... 7376 nodes 11794 edges
localcuts done in 0.31 seconds
Found 30 localcuts in 0.31 seconds
Add 30 cuts (Total 8234), LP: 142337783.225132 (15.59 seconds)
localcuts spheres(8d/10d)... 7300 nodes 11671 edges
localcuts done in 0.35 seconds
Found 23 localcuts in 0.35 seconds
Add 23 cuts (Total 8257), LP: 142337783.225132 (7.49 seconds)
localcuts spheres(9d/11d)... 7295 nodes 11660 edges
localcuts done in 0.32 seconds
Found 23 localcuts in 0.32 seconds
Add 23 cuts (Total 8280), LP: 142337783.225132 (11.75 seconds)
localcuts spheres(10d/12d)... 7246 nodes 11581 edges
localcuts done in 0.38 seconds
Found 26 localcuts in 0.38 seconds
Add 26 cuts (Total 8306), LP: 142337783.225132 (12.60 seconds)
localcuts spheres(11d/13d)... 7331 nodes 11710 edges
localcuts done in 0.43 seconds
Found 30 localcuts in 0.43 seconds
Add 30 cuts (Total 8336), LP: 142337783.225132 (9.28 seconds)
localcuts spheres(12d/14d)... 7254 nodes 11601 edges
localcuts done in 1.50 seconds
Found 47 localcuts in 1.50 seconds
Add 47 cuts (Total 8383), LP: 142337783.225132 (37.28 seconds)
localcuts spheres(13d/15d)... 7317 nodes 11686 edges
localcuts done in 0.64 seconds
Found 71 localcuts in 0.64 seconds
Add 71 cuts (Total 8454), LP: 142337783.225132 (22.51 seconds)
localcuts spheres(14d/16d)... 7289 nodes 11645 edges
localcuts done in 3.17 seconds
Found 42 localcuts in 3.17 seconds
Add 42 cuts (Total 8496), LP: 142337783.225132 (32.75 seconds)
localcuts spheres(15d/17d)... 7270 nodes 11611 edges
localcuts done in 1.01 seconds
Found 59 localcuts in 1.01 seconds
Add 59 cuts (Total 8555), LP: 142337783.225132 (15.33 seconds)
localcuts spheres(16d/18d)... 7279 nodes 11623 edges
localcuts done in 1.15 seconds
Found 68 localcuts in 1.15 seconds
Add 68 cuts (Total 8623), LP: 142337783.225132 (10.87 seconds)
localcuts spheres(17d/19d)... 7303 nodes 11659 edges
localcuts done in 1.01 seconds
Found 42 localcuts in 1.01 seconds
Add 42 cuts (Total 8665), LP: 142337783.225132 (9.56 seconds)
localcuts spheres(18d/20d)... 7296 nodes 11653 edges
localcuts done in 4.82 seconds
Found 32 localcuts in 4.82 seconds
Add 32 cuts (Total 8697), LP: 142337783.225132 (10.90 seconds)
localcuts spheres(19d/21d)... 7389 nodes 11782 edges
localcuts done in 1.37 seconds
Found 54 localcuts in 1.37 seconds
Add 54 cuts (Total 8751), LP: 142337783.225132 (17.16 seconds)
localcuts spheres(20d/22d)... 7378 nodes 11783 edges
localcuts done in 4.72 seconds
Found 42 localcuts in 4.72 seconds
Add 42 cuts (Total 8793), LP: 142337783.225132 (27.17 seconds)
localcuts spheres(21d/23d)... 7303 nodes 11669 edges
localcuts done in 6.61 seconds
Found 62 localcuts in 6.61 seconds
Add 62 cuts (Total 8855), LP: 142337783.225132 (38.33 seconds)
localcuts spheres(22d/24d)... 7273 nodes 11623 edges
localcuts done in 12.51 seconds
Found 104 localcuts in 12.51 seconds
Add 104 cuts (Total 8959), LP: 142337783.225132 (27.45 seconds)
localcuts spheres(23d/25d)... 7337 nodes 11739 edges
localcuts done in 18.47 seconds
Found 46 localcuts in 18.47 seconds
Add 46 cuts (Total 9005), LP: 142337783.225132 (72.42 seconds)
localcuts spheres(24d/26d)... 7253 nodes 11606 edges
localcuts done in 47.17 seconds
Found 70 localcuts in 47.17 seconds
Add 70 cuts (Total 9075), LP: 142337783.225132 (41.56 seconds)
localcuts spheres(25d/27d)... 7261 nodes 11602 edges
localcuts done in 31.45 seconds
Found 78 localcuts in 31.46 seconds
Add 78 cuts (Total 9153), LP: 142337783.225132 (48.50 seconds)
localcuts spheres(26d/28d)... 7299 nodes 11652 edges
-localcuts done in 132.54 seconds
Found 90 localcuts in 132.54 seconds
Add 90 cuts (Total 9243), LP: 142337783.225132 (41.69 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 2.19 seconds (315.36 total in 19 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 7.86 seconds (513.11 total in 19 calls)
(SPARSE) 2 edges added, penalty -0.000000, val 142337783.098142
Time for Sparse edge check: 7.88 seconds (385.73 total in 13 calls)
Write Pool: 200645 cuts
Write Domino Pool: 4548 cuts
Time for Cutting inside loop: 3673.41 seconds (37189.27 total in 13 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 13.43 seconds (526.54 total in 20 calls)
0 edges added, penalty -0.000000
New lower bound: 142337783.098142
Time for Full edge check: 13.46 seconds (141.19 total in 7 calls)
Setting tolerances: next cuts 459.2090 next round 45.9209
LP has: 95143 rows 169120 columns 999570 nonzeros
Loading lp...done in 1.13 seconds
LP has: 95143 rows 169120 columns 999565 nonzeros
Found 500 pool cuts (max viol 2.0000) in 1.04 seconds
Add 370 cuts (Total 9613), LP: 142337783.098142 (61.65 seconds)
Found 500 pool cuts (max viol 4.0000) in 1.00 seconds
Add 392 cuts (Total 8104), LP: 142337783.318533 (52.79 seconds)
Found 469 pool cuts (max viol 3.7412) in 1.07 seconds
Add 275 cuts (Total 7587), LP: 142337783.349378 (30.43 seconds)
Found 303 pool cuts (max viol 3.9572) in 1.04 seconds
Add 185 cuts (Total 7772), LP: 142337783.349378 (5.46 seconds)
Found 141 pool cuts (max viol 0.8182) in 1.04 seconds
Add 27 cuts (Total 7799), LP: 142337783.349378 (2.10 seconds)
Found 116 pool cuts (max viol 0.3333) in 1.04 seconds
Add 10 cuts (Total 7809), LP: 142337783.349378 (1.08 seconds)
Found 106 pool cuts (max viol 0.0020) in 1.03 seconds
Add 0 cuts (Total 7809), LP: 142337783.349378 (0.02 seconds)
Found 60 connect cuts in 0.03 seconds
Add 60 cuts (Total 7869), LP: 142337783.349378 (3.80 seconds)
Found 89 segment cuts in 0.13 seconds
Add 37 cuts (Total 7906), LP: 142337783.349378 (3.45 seconds)
Found 60 fast blossoms in 0.10 seconds
Add 60 cuts (Total 7966), LP: 142337783.349378 (4.33 seconds)
Found 57 Groetschel-Holland blossoms in 0.09 seconds
Add 50 cuts (Total 8016), LP: 142337783.349378 (5.56 seconds)
Block Combs
Type 0: 276 cuts 2.0000 max violation 0.73 seconds
Type 1: 203 cuts 1.9986 max violation 0.71 seconds
Type 2: 186 cuts 1.9980 max violation 0.52 seconds
Type 4: 120 cuts 1.7422 max violation 0.64 seconds
Type 5: 25 cuts 1.7555 max violation 1.21 seconds
Olaf 1: 129 cuts 2.0007 max violation 0.99 seconds
Olaf 2: 125 cuts 1.9993 max violation 0.99 seconds
Olaf 3: 82 cuts 2.0007 max violation 0.91 seconds
Olaf 4: 111 cuts 2.0007 max violation 0.85 seconds
Total Time in block_combs: 8.17
Found 1257 block combs in 8.17 seconds
Add 667 cuts (Total 8683), LP: 142337783.349378 (41.61 seconds)
Found 16 exact subtours in 0.03 seconds
Add 16 cuts (Total 8699), LP: 142337783.349378 (5.58 seconds)
Add 34 cuts (Total 8733), LP: 142337783.349378 (6.99 seconds)
Found 10 exact subtours in 0.02 seconds
Add 10 cuts (Total 8743), LP: 142337783.349378 (1.39 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 8745), LP: 142337783.349378 (1.12 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8746), LP: 142337783.349378 (1.13 seconds)
Found 761 exact subtours in 0.68 seconds
Add 527 cuts (Total 8292), LP: 142337783.996892 (56.71 seconds)
Found 4 exact subtours in 0.03 seconds
Add 4 cuts (Total 8296), LP: 142337783.996892 (3.53 seconds)
Found 409 exact subtours in 0.72 seconds
Add 214 cuts (Total 8510), LP: 142337783.996892 (13.20 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8511), LP: 142337783.996892 (1.08 seconds)
Found 330 exact subtours in 0.55 seconds
Add 144 cuts (Total 8655), LP: 142337783.996892 (9.75 seconds)
Found 235 exact subtours in 0.58 seconds
Add 49 cuts (Total 8704), LP: 142337783.996892 (5.67 seconds)
Found 216 exact subtours in 0.55 seconds
Add 34 cuts (Total 8738), LP: 142337783.996892 (3.42 seconds)
Found 208 exact subtours in 0.50 seconds
Add 25 cuts (Total 8763), LP: 142337783.996892 (2.72 seconds)
Found 190 exact subtours in 0.49 seconds
Add 8 cuts (Total 8771), LP: 142337783.996892 (1.98 seconds)
Found 188 exact subtours in 0.49 seconds
Add 6 cuts (Total 8777), LP: 142337783.996892 (1.71 seconds)
Found 186 exact subtours in 0.51 seconds
Add 4 cuts (Total 8781), LP: 142337783.996892 (1.76 seconds)
Found 186 exact subtours in 0.54 seconds
Add 4 cuts (Total 8785), LP: 142337783.996892 (1.41 seconds)
Found 184 exact subtours in 0.51 seconds
Add 2 cuts (Total 8787), LP: 142337783.996892 (1.19 seconds)
Found 190 exact subtours in 0.53 seconds
Add 8 cuts (Total 8795), LP: 142337783.996892 (1.10 seconds)
Found 183 exact subtours in 0.54 seconds
Add 1 cuts (Total 8796), LP: 142337783.996892 (1.16 seconds)
Found 182 exact subtours in 0.52 seconds
Add 0 cuts (Total 8796), LP: 142337783.996892 (0.02 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 7080, Ecount = 11577
Shrunk ecount = 11289, ncount = 6970
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6970 nodes, and 11289 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6970 nodes, and 11289 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 50 extra paralel edges
GetDual: Not One Eliminated edges: 1
GetDual: Number of loops edges: 2
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 4321 nodes and 22562 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 13
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 17249 dominoes.
Done.
DP Separator: Found 17252 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 1001.580000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2045 / 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 (3055 combs) ...
Found 5000 domino cuts in 1268.77 seconds
Add 1704 cuts (Total 8038), LP: 142337784.210866 (283.79 seconds)
Added 1704 shrunk domino cuts
Found 381 tighten_lp cuts (max viol 2.0000) in 15.36 seconds
Add 318 cuts (Total 8047), LP: 142337785.573456 (110.49 seconds)
Found 27 CLOSE tighten_lp cuts (max viol 0.6484) in 2.12 seconds
Add 27 cuts (Total 8041), LP: 142337785.612950 (25.87 seconds)
Found 242 double deckers (max viol 4.0000) in 14.20 seconds
Add 242 cuts (Total 7387), LP: 142337785.841844 (79.21 seconds)
Found 1 CLOSE double deckers (max viol 0.0294) in 2.01 seconds
Add 1 cuts (Total 7388), LP: 142337785.841844 (1.18 seconds)
Found 756 consecutive ones cuts in 474.61 seconds
Add 445 cuts (Total 7528), LP: 142337785.905073 (51.36 seconds)
localcuts spheres(6d/8d)... 6303 nodes 10102 edges
localcuts done in 0.14 seconds
Found 5 localcuts in 0.14 seconds
Add 5 cuts (Total 7533), LP: 142337785.905073 (7.60 seconds)
localcuts spheres(7d/9d)... 6322 nodes 10129 edges
localcuts done in 0.19 seconds
Found 12 localcuts in 0.19 seconds
Add 12 cuts (Total 7545), LP: 142337785.905073 (5.00 seconds)
localcuts spheres(8d/10d)... 6423 nodes 10270 edges
localcuts done in 0.20 seconds
Found 16 localcuts in 0.20 seconds
Add 16 cuts (Total 7561), LP: 142337785.905073 (4.70 seconds)
localcuts spheres(9d/11d)... 6473 nodes 10339 edges
localcuts done in 0.20 seconds
Found 25 localcuts in 0.20 seconds
Add 25 cuts (Total 7586), LP: 142337785.905073 (13.28 seconds)
localcuts spheres(10d/12d)... 6341 nodes 10157 edges
localcuts done in 0.47 seconds
Found 22 localcuts in 0.47 seconds
Add 22 cuts (Total 7608), LP: 142337785.905073 (3.08 seconds)
localcuts spheres(11d/13d)... 6372 nodes 10209 edges
localcuts done in 0.39 seconds
Found 15 localcuts in 0.39 seconds
Add 15 cuts (Total 7623), LP: 142337785.905073 (5.60 seconds)
localcuts spheres(12d/14d)... 6292 nodes 10084 edges
localcuts done in 0.21 seconds
Found 15 localcuts in 0.21 seconds
Add 15 cuts (Total 7638), LP: 142337785.905073 (5.79 seconds)
localcuts spheres(13d/15d)... 6319 nodes 10128 edges
localcuts done in 0.62 seconds
Found 31 localcuts in 0.62 seconds
Add 31 cuts (Total 7669), LP: 142337785.905073 (7.84 seconds)
localcuts spheres(14d/16d)... 6324 nodes 10146 edges
localcuts done in 0.25 seconds
Found 6 localcuts in 0.25 seconds
Add 6 cuts (Total 7675), LP: 142337785.905073 (1.44 seconds)
localcuts spheres(15d/17d)... 6330 nodes 10153 edges
localcuts done in 0.28 seconds
Found 6 localcuts in 0.28 seconds
Add 6 cuts (Total 7681), LP: 142337785.905073 (2.56 seconds)
localcuts spheres(16d/18d)... 6341 nodes 10175 edges
localcuts done in 0.23 seconds
Found 9 localcuts in 0.23 seconds
Add 9 cuts (Total 7690), LP: 142337785.905073 (3.09 seconds)
localcuts spheres(17d/19d)... 6345 nodes 10188 edges
localcuts done in 0.39 seconds
Found 17 localcuts in 0.39 seconds
Add 17 cuts (Total 7707), LP: 142337785.905073 (2.06 seconds)
localcuts spheres(18d/20d)... 6398 nodes 10267 edges
localcuts done in 0.66 seconds
Found 34 localcuts in 0.66 seconds
Add 34 cuts (Total 7741), LP: 142337785.905073 (6.34 seconds)
localcuts spheres(19d/21d)... 6369 nodes 10214 edges
localcuts done in 4.23 seconds
Found 50 localcuts in 4.23 seconds
Add 50 cuts (Total 7791), LP: 142337785.905073 (8.35 seconds)
localcuts spheres(20d/22d)... 6353 nodes 10193 edges
localcuts done in 9.65 seconds
Found 45 localcuts in 9.65 seconds
Add 45 cuts (Total 7836), LP: 142337785.905073 (3.68 seconds)
localcuts spheres(21d/23d)... 6404 nodes 10272 edges
localcuts done in 1.65 seconds
Found 29 localcuts in 1.65 seconds
Add 29 cuts (Total 7865), LP: 142337785.905073 (3.67 seconds)
localcuts spheres(22d/24d)... 6390 nodes 10257 edges
localcuts done in 3.06 seconds
Found 21 localcuts in 3.06 seconds
Add 21 cuts (Total 7886), LP: 142337785.905073 (14.18 seconds)
localcuts spheres(23d/25d)... 6352 nodes 10190 edges
localcuts done in 7.46 seconds
Found 26 localcuts in 7.46 seconds
Add 26 cuts (Total 7912), LP: 142337785.905073 (15.50 seconds)
localcuts spheres(24d/26d)... 6350 nodes 10182 edges
localcuts done in 10.93 seconds
Found 19 localcuts in 10.93 seconds
Add 19 cuts (Total 7931), LP: 142337785.905073 (5.68 seconds)
localcuts spheres(25d/27d)... 6358 nodes 10207 edges
localcuts done in 13.87 seconds
Found 27 localcuts in 13.87 seconds
Add 27 cuts (Total 7958), LP: 142337785.905073 (6.80 seconds)
localcuts spheres(26d/28d)... 6381 nodes 10223 edges
localcuts done in 16.53 seconds
Found 24 localcuts in 16.53 seconds
Add 24 cuts (Total 7982), LP: 142337785.905073 (10.42 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 2.15 seconds (317.51 total in 20 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 7.72 seconds (534.26 total in 21 calls)
(SPARSE) 2 edges added, penalty -0.000000, val 142337785.905073
Time for Sparse edge check: 7.73 seconds (393.46 total in 14 calls)
Write Pool: 201594 cuts
Write Domino Pool: 5038 cuts
Time for Cutting inside loop: 2966.35 seconds (40155.62 total in 14 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.23 seconds (318.74 total in 21 calls)
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 27.44 seconds (561.70 total in 22 calls)
2 edges added, penalty -0.000000
New lower bound: 142337785.905073
Time for Full edge check: 27.46 seconds (168.65 total in 8 calls)
Time for Cutting Loop: 6684.50 seconds (40339.70 total in 4 calls)
Number of outside rounds: 2
SETTING MAXCHUNKSIZE = 32
Setting tolerances: next cuts 459.1809 next round 45.9181
CCtsp_init_edgegenerator (50)
..................................................................................... 2361770 edges
LP has: 93882 rows 169124 columns 995419 nonzeros
Loading lp...done in 1.11 seconds
LP has: 93882 rows 169124 columns 995386 nonzeros
Found 500 pool cuts (max viol 3.0000) in 1.04 seconds
Add 384 cuts (Total 8366), LP: 142337785.905073 (66.08 seconds)
Found 500 pool cuts (max viol 2.2494) in 1.07 seconds
Add 347 cuts (Total 7421), LP: 142337786.021003 (51.80 seconds)
Found 355 pool cuts (max viol 2.0000) in 1.03 seconds
Add 270 cuts (Total 7394), LP: 142337786.508324 (31.78 seconds)
Found 309 pool cuts (max viol 1.3333) in 1.06 seconds
Add 214 cuts (Total 7374), LP: 142337786.551090 (17.18 seconds)
Found 61 pool cuts (max viol 1.9998) in 1.06 seconds
Add 56 cuts (Total 7430), LP: 142337786.551090 (3.20 seconds)
Found 35 pool cuts (max viol 0.2207) in 1.02 seconds
Add 30 cuts (Total 7460), LP: 142337786.551090 (2.13 seconds)
Found 19 pool cuts (max viol 0.6667) in 1.04 seconds
Add 14 cuts (Total 7474), LP: 142337786.551090 (1.51 seconds)
Found 7 pool cuts (max viol 0.0138) in 1.04 seconds
Add 2 cuts (Total 7476), LP: 142337786.551090 (1.11 seconds)
Found 6 pool cuts (max viol 0.0261) in 1.04 seconds
Add 1 cuts (Total 7477), LP: 142337786.551090 (1.09 seconds)
Found 5 pool cuts (max viol 0.0013) in 1.03 seconds
Add 0 cuts (Total 7477), LP: 142337786.551090 (0.01 seconds)
Found 47 connect cuts in 0.03 seconds
Add 47 cuts (Total 7524), LP: 142337786.551090 (3.07 seconds)
Found 73 segment cuts in 0.13 seconds
Add 47 cuts (Total 7380), LP: 142337791.589723 (9.44 seconds)
Found 62 fast blossoms in 0.08 seconds
Add 62 cuts (Total 7442), LP: 142337791.589723 (3.86 seconds)
Found 48 Groetschel-Holland blossoms in 0.07 seconds
Add 46 cuts (Total 7458), LP: 142337791.823077 (5.40 seconds)
Block Combs
Type 0: 264 cuts 1.9998 max violation 0.90 seconds
Type 1: 214 cuts 1.9997 max violation 0.79 seconds
Type 2: 183 cuts 3.4364 max violation 0.67 seconds
Type 4: 139 cuts 3.5773 max violation 0.57 seconds
Type 5: 21 cuts 1.6477 max violation 0.96 seconds
Olaf 1: 156 cuts 1.9996 max violation 0.90 seconds
Olaf 2: 153 cuts 1.9998 max violation 1.08 seconds
Olaf 3: 112 cuts 2.0000 max violation 0.84 seconds
Olaf 4: 108 cuts 2.0000 max violation 0.78 seconds
Total Time in block_combs: 8.11
Found 1350 block combs in 8.11 seconds
Add 766 cuts (Total 7573), LP: 142337792.167210 (44.50 seconds)
Found 35 exact subtours in 0.04 seconds
Add 35 cuts (Total 7608), LP: 142337792.167210 (4.38 seconds)
Add 29 cuts (Total 7637), LP: 142337792.167210 (5.06 seconds)
Found 11 exact subtours in 0.03 seconds
Add 11 cuts (Total 7648), LP: 142337792.167210 (5.32 seconds)
Found 6 exact subtours in 0.03 seconds
Add 6 cuts (Total 7654), LP: 142337792.167210 (1.08 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7655), LP: 142337792.167210 (1.07 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7656), LP: 142337792.167210 (1.06 seconds)
Found 702 exact subtours in 0.66 seconds
Add 500 cuts (Total 8156), LP: 142337792.167210 (37.68 seconds)
Found 3 exact subtours in 0.03 seconds
Add 3 cuts (Total 8159), LP: 142337792.167210 (1.13 seconds)
Found 2 exact subtours in 0.02 seconds
Add 2 cuts (Total 8161), LP: 142337792.167210 (1.05 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 8162), LP: 142337792.167210 (1.11 seconds)
Found 354 exact subtours in 0.62 seconds
Add 215 cuts (Total 8377), LP: 142337792.167210 (14.45 seconds)
Found 234 exact subtours in 0.52 seconds
Add 84 cuts (Total 8461), LP: 142337792.167210 (6.48 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 8463), LP: 142337792.167210 (1.09 seconds)
Found 193 exact subtours in 0.55 seconds
Add 45 cuts (Total 8508), LP: 142337792.167210 (3.48 seconds)
Found 170 exact subtours in 0.52 seconds
Add 21 cuts (Total 8529), LP: 142337792.167210 (2.43 seconds)
Found 157 exact subtours in 0.52 seconds
Add 9 cuts (Total 8538), LP: 142337792.167210 (1.88 seconds)
Found 158 exact subtours in 0.53 seconds
Add 8 cuts (Total 8546), LP: 142337792.167210 (2.06 seconds)
Found 151 exact subtours in 0.55 seconds
Add 3 cuts (Total 8549), LP: 142337792.167210 (1.41 seconds)
Found 150 exact subtours in 0.54 seconds
Add 2 cuts (Total 8551), LP: 142337792.167210 (1.24 seconds)
Found 149 exact subtours in 0.54 seconds
Add 1 cuts (Total 8552), LP: 142337792.167210 (1.18 seconds)
Found 149 exact subtours in 0.55 seconds
Add 1 cuts (Total 8553), LP: 142337792.167210 (1.11 seconds)
Found 148 exact subtours in 0.54 seconds
Add 0 cuts (Total 8553), LP: 142337792.167210 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 6757, Ecount = 10998
Shrunk ecount = 10710, ncount = 6635
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6635 nodes, and 10710 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6635 nodes, and 10710 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 2 trivial dominos
GetDual: graph still has 72 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 2
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 4077 nodes and 21408 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 14
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 15534 dominoes.
Done.
DP Separator: Found 15536 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 981.180000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2206 / 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 (2950 combs) ...
Found 5000 domino cuts in 1226.55 seconds
Add 1638 cuts (Total 7876), LP: 142337796.431457 (186.47 seconds)
Added 1638 shrunk domino cuts
Found 242 tighten_lp cuts (max viol 1.0000) in 13.50 seconds
Add 242 cuts (Total 7940), LP: 142337798.299753 (51.79 seconds)
Found 77 CLOSE tighten_lp cuts (max viol 0.9702) in 1.74 seconds
Add 77 cuts (Total 7840), LP: 142337803.063685 (25.53 seconds)
Found 247 double deckers (max viol 3.4998) in 15.81 seconds
Add 247 cuts (Total 7954), LP: 142337805.234028 (58.91 seconds)
Found 10 CLOSE double deckers (max viol 0.4664) in 2.08 seconds
Add 10 cuts (Total 7872), LP: 142337805.283598 (6.01 seconds)
Found 695 consecutive ones cuts in 291.70 seconds
Add 504 cuts (Total 7804), LP: 142337807.107581 (73.80 seconds)
localcuts classes(8d)... 6831 nodes 10990 edges
localcuts done in 0.19 seconds
Found 18 localcuts in 0.19 seconds
Add 18 cuts (Total 7822), LP: 142337807.107581 (5.76 seconds)
localcuts classes(9d)... 6810 nodes 10970 edges
localcuts done in 0.21 seconds
Found 29 localcuts in 0.21 seconds
Add 29 cuts (Total 7851), LP: 142337807.107581 (7.96 seconds)
localcuts classes(10d)... 6903 nodes 11105 edges
localcuts done in 0.24 seconds
Found 25 localcuts in 0.24 seconds
Add 25 cuts (Total 7876), LP: 142337807.107581 (6.64 seconds)
localcuts classes(11d)... 6927 nodes 11130 edges
localcuts done in 0.38 seconds
Found 23 localcuts in 0.38 seconds
Add 23 cuts (Total 7628), LP: 142337807.155646 (8.37 seconds)
localcuts classes(12d)... 6826 nodes 10932 edges
localcuts done in 0.27 seconds
Found 31 localcuts in 0.27 seconds
Add 31 cuts (Total 7659), LP: 142337807.155646 (4.76 seconds)
localcuts classes(13d)... 6860 nodes 10982 edges
localcuts done in 0.25 seconds
Found 21 localcuts in 0.25 seconds
Add 21 cuts (Total 7680), LP: 142337807.155646 (5.14 seconds)
localcuts classes(14d)... 6829 nodes 10935 edges
localcuts done in 0.29 seconds
Found 20 localcuts in 0.29 seconds
Add 20 cuts (Total 7700), LP: 142337807.155646 (4.39 seconds)
localcuts classes(15d)... 6901 nodes 11055 edges
localcuts done in 0.38 seconds
Found 29 localcuts in 0.38 seconds
Add 29 cuts (Total 7729), LP: 142337807.155646 (11.76 seconds)
localcuts classes(16d)... 6977 nodes 11169 edges
localcuts done in 0.68 seconds
Found 26 localcuts in 0.68 seconds
Add 26 cuts (Total 7755), LP: 142337807.155646 (5.87 seconds)
localcuts classes(17d)... 6952 nodes 11129 edges
localcuts done in 0.47 seconds
Found 26 localcuts in 0.47 seconds
Add 26 cuts (Total 7781), LP: 142337807.155646 (8.07 seconds)
localcuts classes(18d)... 6960 nodes 11148 edges
localcuts done in 0.32 seconds
Found 26 localcuts in 0.32 seconds
Add 26 cuts (Total 7807), LP: 142337807.155646 (12.01 seconds)
localcuts classes(19d)... 6816 nodes 10936 edges
localcuts done in 2.66 seconds
Found 20 localcuts in 2.66 seconds
Add 20 cuts (Total 7827), LP: 142337807.155646 (5.41 seconds)
localcuts classes(20d)... 6838 nodes 10977 edges
localcuts done in 1.18 seconds
Found 18 localcuts in 1.18 seconds
Add 18 cuts (Total 7845), LP: 142337807.155646 (3.01 seconds)
localcuts classes(21d)... 6837 nodes 10967 edges
localcuts done in 1.32 seconds
Found 12 localcuts in 1.32 seconds
Add 12 cuts (Total 7857), LP: 142337807.155646 (3.62 seconds)
localcuts classes(22d)... 6826 nodes 10949 edges
localcuts done in 2.49 seconds
Found 12 localcuts in 2.49 seconds
Add 12 cuts (Total 7869), LP: 142337807.155646 (2.31 seconds)
localcuts classes(23d)... 6758 nodes 10843 edges
localcuts done in 0.41 seconds
Found 14 localcuts in 0.41 seconds
Add 14 cuts (Total 7883), LP: 142337807.155646 (3.01 seconds)
localcuts classes(24d)... 6753 nodes 10840 edges
localcuts done in 3.22 seconds
Found 15 localcuts in 3.22 seconds
Add 15 cuts (Total 7898), LP: 142337807.155646 (3.56 seconds)
localcuts classes(25d)... 6780 nodes 10869 edges
localcuts done in 0.45 seconds
Found 9 localcuts in 0.45 seconds
Add 9 cuts (Total 7907), LP: 142337807.155646 (2.97 seconds)
localcuts classes(26d)... 6741 nodes 10810 edges
-localcuts done in 5.60 seconds
Found 10 localcuts in 5.60 seconds
Add 10 cuts (Total 7917), LP: 142337807.155646 (2.30 seconds)
localcuts classes(27d)... 6763 nodes 10839 edges
-localcuts done in 4.84 seconds
Found 9 localcuts in 4.84 seconds
Add 9 cuts (Total 7926), LP: 142337807.155646 (5.83 seconds)
localcuts classes(28d)... 6798 nodes 10891 edges
-localcuts done in 1.08 seconds
Found 11 localcuts in 1.08 seconds
Add 11 cuts (Total 7937), LP: 142337807.155646 (4.35 seconds)
localcuts classes(29d)... 6859 nodes 10992 edges
-localcuts done in 1.11 seconds
Found 11 localcuts in 1.11 seconds
Add 11 cuts (Total 7948), LP: 142337807.155646 (1.45 seconds)
localcuts classes(30d)... 6880 nodes 11015 edges
--------localcuts done in 27.54 seconds
Found 7 localcuts in 27.54 seconds
Add 7 cuts (Total 7872), LP: 142337808.054058 (19.19 seconds)
localcuts classes(31d)... 7000 nodes 11171 edges
-----CCchunk_oracle node limit exceeded
tilt failed
ADDING POSSIBLE NON-FACET
-------------localcuts done in 39.48 seconds
Found 7 localcuts in 39.48 seconds
Add 7 cuts (Total 7098), LP: 142337808.634810 (25.90 seconds)
localcuts classes(32d)... 5703 nodes 9067 edges
----localcuts done in 21.89 seconds
Found 50 localcuts in 21.89 seconds
Add 50 cuts (Total 7073), LP: 142337809.072912 (14.15 seconds)
localcuts spheres(6d/8d)... 5829 nodes 9255 edges
localcuts done in 0.13 seconds
localcuts spheres(7d/9d)... 5829 nodes 9255 edges
localcuts done in 0.12 seconds
localcuts spheres(8d/10d)... 5829 nodes 9255 edges
localcuts done in 0.13 seconds
localcuts spheres(9d/11d)... 5829 nodes 9255 edges
localcuts done in 0.11 seconds
localcuts spheres(10d/12d)... 5829 nodes 9255 edges
localcuts done in 0.12 seconds
localcuts spheres(11d/13d)... 5829 nodes 9255 edges
localcuts done in 0.15 seconds
localcuts spheres(12d/14d)... 5829 nodes 9255 edges
localcuts done in 0.13 seconds
localcuts spheres(13d/15d)... 5829 nodes 9255 edges
localcuts done in 0.12 seconds
localcuts spheres(14d/16d)... 5829 nodes 9255 edges
localcuts done in 0.13 seconds
Found 1 localcuts in 0.13 seconds
Add 1 cuts (Total 7074), LP: 142337809.072912 (1.10 seconds)
localcuts spheres(15d/17d)... 5832 nodes 9260 edges
localcuts done in 0.13 seconds
localcuts spheres(16d/18d)... 5832 nodes 9260 edges
localcuts done in 0.13 seconds
localcuts spheres(17d/19d)... 5832 nodes 9260 edges
localcuts done in 0.12 seconds
localcuts spheres(18d/20d)... 5832 nodes 9260 edges
localcuts done in 0.12 seconds
localcuts spheres(19d/21d)... 5832 nodes 9260 edges
localcuts done in 0.14 seconds
localcuts spheres(20d/22d)... 5832 nodes 9260 edges
localcuts done in 0.13 seconds
localcuts spheres(21d/23d)... 5832 nodes 9260 edges
localcuts done in 0.10 seconds
localcuts spheres(22d/24d)... 5832 nodes 9260 edges
localcuts done in 0.12 seconds
localcuts spheres(23d/25d)... 5832 nodes 9260 edges
localcuts done in 0.10 seconds
localcuts spheres(24d/26d)... 5832 nodes 9260 edges
localcuts done in 0.12 seconds
localcuts spheres(25d/27d)... 5832 nodes 9260 edges
localcuts done in 0.09 seconds
localcuts spheres(26d/28d)... 5832 nodes 9260 edges
localcuts done in 0.11 seconds
localcuts spheres(27d/29d)... 5832 nodes 9260 edges
localcuts done in 0.09 seconds
localcuts spheres(28d/30d)... 5832 nodes 9260 edges
localcuts done in 0.12 seconds
localcuts spheres(29d/31d)... 5832 nodes 9260 edges
localcuts done in 0.12 seconds
localcuts spheres(30d/32d)... 5832 nodes 9260 edges
localcuts done in 0.11 seconds
CCtsp_generate_edges (277700)
Time for Add edges optimize: 0.76 seconds (319.50 total in 22 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 5.23 seconds (566.93 total in 23 calls)
(SPARSE) 1 edges added, penalty -0.000000, val 142337809.072912
Time for Sparse edge check: 5.24 seconds (398.70 total in 15 calls)
Write Pool: 202804 cuts
Write Domino Pool: 5338 cuts
Time for Cutting inside loop: 2691.99 seconds (42847.61 total in 15 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 11.99 seconds (578.92 total in 24 calls)
0 edges added, penalty -0.000000
New lower bound: 142337809.072912
Time for Full edge check: 12.03 seconds (180.68 total in 9 calls)
Setting tolerances: next cuts 458.9493 next round 45.8949
LP has: 92974 rows 169125 columns 849655 nonzeros
Loading lp...done in 0.71 seconds
LP has: 92974 rows 169125 columns 849653 nonzeros
Found 500 pool cuts (max viol 9.9957) in 1.04 seconds
Add 457 cuts (Total 7144), LP: 142337810.103239 (32.83 seconds)
Found 500 pool cuts (max viol 2.9891) in 1.06 seconds
Add 475 cuts (Total 7619), LP: 142337810.103239 (14.19 seconds)
Found 423 pool cuts (max viol 1.6000) in 1.04 seconds
Add 267 cuts (Total 7359), LP: 142337810.807056 (20.95 seconds)
Found 165 pool cuts (max viol 2.0000) in 1.09 seconds
Add 106 cuts (Total 7246), LP: 142337810.987541 (9.03 seconds)
Found 176 pool cuts (max viol 2.0000) in 1.06 seconds
Add 136 cuts (Total 7304), LP: 142337810.996042 (5.37 seconds)
Found 63 pool cuts (max viol 1.1828) in 1.08 seconds
Add 28 cuts (Total 7332), LP: 142337810.996042 (1.46 seconds)
Found 35 pool cuts (max viol 0.1179) in 1.06 seconds
Add 4 cuts (Total 7336), LP: 142337810.996042 (1.26 seconds)
Found 31 pool cuts (max viol 0.0019) in 1.05 seconds
Add 0 cuts (Total 7336), LP: 142337810.996042 (0.02 seconds)
Found 90 connect cuts in 0.03 seconds
Add 90 cuts (Total 7426), LP: 142337810.996042 (2.97 seconds)
Found 92 segment cuts in 0.13 seconds
Add 41 cuts (Total 7352), LP: 142337811.102117 (5.00 seconds)
Found 74 fast blossoms in 0.09 seconds
Add 74 cuts (Total 7426), LP: 142337811.102117 (2.55 seconds)
Found 72 Groetschel-Holland blossoms in 0.09 seconds
Add 69 cuts (Total 7495), LP: 142337811.102117 (9.08 seconds)
Block Combs
Type 0: 321 cuts 2.0000 max violation 0.80 seconds
Type 1: 229 cuts 1.9696 max violation 0.75 seconds
Type 2: 172 cuts 1.9696 max violation 0.55 seconds
Type 4: 146 cuts 1.8734 max violation 0.48 seconds
Type 5: 19 cuts 1.0545 max violation 1.33 seconds
Olaf 1: 158 cuts 1.7586 max violation 0.93 seconds
Olaf 2: 147 cuts 1.7151 max violation 0.97 seconds
Olaf 3: 78 cuts 1.8732 max violation 0.68 seconds
Olaf 4: 81 cuts 1.8732 max violation 0.93 seconds
Total Time in block_combs: 8.05
Found 1351 block combs in 8.05 seconds
Add 759 cuts (Total 7457), LP: 142337811.472237 (37.18 seconds)
Found 29 exact subtours in 0.03 seconds
Add 29 cuts (Total 7486), LP: 142337811.472237 (5.84 seconds)
Add 21 cuts (Total 7507), LP: 142337811.472237 (2.86 seconds)
Found 12 exact subtours in 0.03 seconds
Add 12 cuts (Total 7519), LP: 142337811.472237 (1.07 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7521), LP: 142337811.472237 (1.09 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7522), LP: 142337811.472237 (1.02 seconds)
Found 688 exact subtours in 0.56 seconds
Add 474 cuts (Total 7996), LP: 142337811.472237 (30.26 seconds)
Found 6 exact subtours in 0.03 seconds
Add 6 cuts (Total 8002), LP: 142337811.472237 (1.16 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 8003), LP: 142337811.472237 (1.03 seconds)
Found 388 exact subtours in 0.61 seconds
Add 209 cuts (Total 8212), LP: 142337811.472237 (12.34 seconds)
Found 281 exact subtours in 0.44 seconds
Add 95 cuts (Total 8307), LP: 142337811.472237 (6.25 seconds)
Found 1 exact subtours in 0.02 seconds
Add 1 cuts (Total 8308), LP: 142337811.472237 (1.09 seconds)
Found 218 exact subtours in 0.54 seconds
Add 31 cuts (Total 8339), LP: 142337811.472237 (4.43 seconds)
Found 215 exact subtours in 0.47 seconds
Add 32 cuts (Total 8371), LP: 142337811.472237 (3.10 seconds)
Found 192 exact subtours in 0.45 seconds
Add 13 cuts (Total 8384), LP: 142337811.472237 (2.37 seconds)
Found 188 exact subtours in 0.48 seconds
Add 7 cuts (Total 8391), LP: 142337811.472237 (1.50 seconds)
Found 185 exact subtours in 0.50 seconds
Add 5 cuts (Total 7911), LP: 142337816.766142 (9.05 seconds)
Found 211 exact subtours in 0.61 seconds
Add 53 cuts (Total 7841), LP: 142337820.180393 (29.10 seconds)
Found 287 exact subtours in 0.55 seconds
Add 87 cuts (Total 7551), LP: 142337822.020511 (16.69 seconds)
Found 5 exact subtours in 0.01 seconds
Add 5 cuts (Total 7556), LP: 142337822.020511 (1.05 seconds)
Found 2 exact subtours in 0.03 seconds
Add 2 cuts (Total 7558), LP: 142337822.020511 (1.04 seconds)
Found 1 exact subtours in 0.03 seconds
Add 1 cuts (Total 7559), LP: 142337822.020511 (1.03 seconds)
Found 412 exact subtours in 0.58 seconds
Add 139 cuts (Total 7619), LP: 142337823.669710 (28.73 seconds)
Found 206 exact subtours in 0.50 seconds
Add 39 cuts (Total 7658), LP: 142337823.669710 (4.55 seconds)
Found 180 exact subtours in 0.51 seconds
Add 15 cuts (Total 7673), LP: 142337823.669710 (1.75 seconds)
Found 165 exact subtours in 0.49 seconds
Add 1 cuts (Total 7674), LP: 142337823.669710 (1.04 seconds)
Found 165 exact subtours in 0.49 seconds
Add 1 cuts (Total 7675), LP: 142337823.669710 (1.02 seconds)
Found 162 exact subtours in 0.50 seconds
Add 0 cuts (Total 7675), LP: 142337823.669710 (0.03 seconds)
Call DPseparator with shrinking ...
Use Domino Boss: tiara49
Safe Shrinking: Ncount = 6279, Ecount = 10232
Shrunk ecount = 9857, ncount = 6106
DP Separator: Noss name = tiara49.
Saving graph (binary format) to file graph.b.x ... done.
DP Separator: Graph G^* has 6106 nodes, and 9857 edges.
DP Separator: Eliminated 0 edges of value less than 0.000001.
DP Separator: Graph G^* now has 6106 nodes, and 9857 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 2 trivial dominos
GetDual: graph still has 76 extra paralel edges
GetDual: Not One Eliminated edges: 0
GetDual: Number of loops edges: 2
DP Separator: G^* is connected.
DP Separator: Bi-directed dual graph (after contraction of consecutive ones) has 3753 nodes and 19700 edges.
DP Separator: Looking for dual dominoes.
Host: tiara49 Current process id: 8913
Sending graph id = 15
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 14206 dominoes.
Done.
DP Separator: Found 14208 dual dominoes.
DP Separator: Computing dual constraints.
DP Separator: DDP Heuristic: ON. Time Limit = 1000.000000.
DP Separator: Total heuristic running time: 959.600000 seconds.
DP Separator: Found 5000 dual DP-Constraints.
DP Separator: 2257 / 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 (3154 combs) ...
Found 5000 domino cuts in 1153.09 seconds
Add 1650 cuts (Total 9325), LP: 142337823.669710 (219.32 seconds)
Added 1650 shrunk domino cuts
Found 231 tighten_lp cuts (max viol 1.0002) in 15.93 seconds
Add 231 cuts (Total 8022), LP: 142337828.882229 (46.15 seconds)
Found 10 CLOSE tighten_lp cuts (max viol 0.2500) in 2.06 seconds
Add 10 cuts (Total 7968), LP: 142337828.897223 (8.04 seconds)
Found 190 double deckers (max viol 3.0000) in 14.54 seconds
Add 190 cuts (Total 7946), LP: 142337828.921383 (35.71 seconds)
Found 7 CLOSE double deckers (max viol 0.2053) in 2.22 seconds
Add 7 cuts (Total 7953), LP: 142337828.921383 (1.55 seconds)
Found 697 consecutive ones cuts in 266.26 seconds
Add 502 cuts (Total 7701), LP: 142337829.789410 (56.70 seconds)
localcuts spheres(6d/8d)... 7071 nodes 11416 edges
localcuts done in 0.54 seconds
Found 48 localcuts in 0.54 seconds
Add 48 cuts (Total 7749), LP: 142337829.789410 (4.14 seconds)
localcuts spheres(7d/9d)... 7098 nodes 11447 edges
localcuts done in 0.27 seconds
Found 20 localcuts in 0.27 seconds
Add 20 cuts (Total 7769), LP: 142337829.789410 (4.52 seconds)
localcuts spheres(8d/10d)... 7056 nodes 11390 edges
localcuts done in 0.24 seconds
Found 9 localcuts in 0.24 seconds
Add 9 cuts (Total 7778), LP: 142337829.789410 (2.10 seconds)
localcuts spheres(9d/11d)... 7070 nodes 11415 edges
localcuts done in 0.28 seconds
Found 33 localcuts in 0.28 seconds
Add 33 cuts (Total 7811), LP: 142337829.789410 (3.00 seconds)
localcuts spheres(10d/12d)... 7134 nodes 11508 edges
localcuts done in 0.64 seconds
Found 8 localcuts in 0.64 seconds
Add 8 cuts (Total 7819), LP: 142337829.789410 (2.50 seconds)
localcuts spheres(11d/13d)... 7142 nodes 11519 edges
localcuts done in 0.46 seconds
Found 44 localcuts in 0.46 seconds
Add 44 cuts (Total 7863), LP: 142337829.789410 (7.35 seconds)
localcuts spheres(12d/14d)... 7052 nodes 11382 edges
localcuts done in 1.57 seconds
Found 157 localcuts in 1.57 seconds
Add 157 cuts (Total 8020), LP: 142337829.789410 (8.89 seconds)
localcuts spheres(13d/15d)... 7296 nodes 11755 edges
localcuts done in 0.86 seconds
Found 46 localcuts in 0.86 seconds
Add 46 cuts (Total 8066), LP: 142337829.789410 (7.93 seconds)
localcuts spheres(14d/16d)... 7268 nodes 11702 edges
localcuts done in 0.99 seconds
Found 32 localcuts in 0.99 seconds
Add 32 cuts (Total 8098), LP: 142337829.789410 (4.12 seconds)
localcuts spheres(15d/17d)... 7236 nodes 11648 edges
localcuts done in 0.37 seconds
Found 32 localcuts in 0.37 seconds
Add 32 cuts (Total 8130), LP: 142337829.789410 (2.34 seconds)
localcuts spheres(16d/18d)... 7216 nodes 11621 edges
localcuts done in 1.95 seconds
Found 27 localcuts in 1.95 seconds
Add 27 cuts (Total 8157), LP: 142337829.789410 (1.67 seconds)
localcuts spheres(17d/19d)... 7230 nodes 11650 edges
localcuts done in 1.09 seconds
Found 24 localcuts in 1.09 seconds
Add 24 cuts (Total 8181), LP: 142337829.789410 (3.54 seconds)
localcuts spheres(18d/20d)... 7357 nodes 11838 edges
localcuts done in 5.90 seconds
Found 49 localcuts in 5.90 seconds
Add 49 cuts (Total 8230), LP: 142337829.789410 (3.84 seconds)
localcuts spheres(19d/21d)... 7310 nodes 11773 edges
localcuts done in 3.39 seconds
Found 17 localcuts in 3.39 seconds
Add 17 cuts (Total 8247), LP: 142337829.789410 (3.14 seconds)
localcuts spheres(20d/22d)... 7363 nodes 11860 edges
localcuts done in 8.59 seconds
Found 64 localcuts in 8.59 seconds
Add 64 cuts (Total 8311), LP: 142337829.789410 (6.09 seconds)
localcuts spheres(21d/23d)... 7345 nodes 11828 edges
localcuts done in 1.62 seconds
Found 31 localcuts in 1.62 seconds
Add 31 cuts (Total 8342), LP: 142337829.789410 (3.73 seconds)
localcuts spheres(22d/24d)... 7342 nodes 11839 edges
localcuts done in 3.51 seconds
Found 32 localcuts in 3.51 seconds
Add 32 cuts (Total 8374), LP: 142337829.789410 (4.10 seconds)
localcuts spheres(23d/25d)... 7314 nodes 11793 edges
localcuts done in 0.79 seconds
Found 26 localcuts in 0.79 seconds
Add 26 cuts (Total 8400), LP: 142337829.789410 (3.13 seconds)
localcuts spheres(24d/26d)... 7317 nodes 11787 edges
localcuts done in 5.19 seconds
Found 9 localcuts in 5.19 seconds
Add 9 cuts (Total 8409), LP: 142337829.789410 (1.78 seconds)
localcuts spheres(25d/27d)... 7271 nodes 11718 edges
localcuts done in 0.64 seconds
Found 8 localcuts in 0.64 seconds
Add 8 cuts (Total 8417), LP: 142337829.789410 (1.26 seconds)
localcuts spheres(26d/28d)... 7276 nodes 11725 edges
localcuts done in 0.36 seconds
Found 1 localcuts in 0.36 seconds
Add 1 cuts (Total 8418), LP: 142337829.789410 (2.16 seconds)
localcuts spheres(27d/29d)... 7333 nodes 11824 edges
localcuts done in 1.73 seconds
Found 8 localcuts in 1.73 seconds
Add 8 cuts (Total 8426), LP: 142337829.789410 (5.44 seconds)
localcuts spheres(28d/30d)... 7340 nodes 11830 edges
localcuts done in 3.07 seconds
Found 10 localcuts in 3.07 seconds
Add 10 cuts (Total 8436), LP: 142337829.789410 (2.98 seconds)
localcuts spheres(29d/31d)... 7338 nodes 11819 edges
localcuts done in 5.72 seconds
Found 19 localcuts in 5.72 seconds
Add 19 cuts (Total 8455), LP: 142337829.789410 (5.92 seconds)
localcuts spheres(30d/32d)... 7314 nodes 11779 edges
localcuts done in 15.37 seconds
Found 26 localcuts in 15.37 seconds
Add 26 cuts (Total 8481), LP: 142337829.789410 (9.73 seconds)
CCtsp_generate_edges (277700)
Time for Add edges optimize: 1.22 seconds (320.72 total in 23 calls)
CCtsp_generate_edges (277700)
Time for Add edges: 6.55 seconds (585.47 total in 25 calls)
(SPARSE) 1 edges added, penalty -0.000000, val 142337829.789410
Time for Sparse edge check: 6.56 seconds (405.26 total in 16 calls)
Write Pool: 203575 cuts
Write Domino Pool: 5642 cuts
Time for Cutting inside loop: 2399.89 seconds (45247.50 total in 16 calls)
CCtsp_init_edgegenerator (-1)
xprice_build
xprice_reset (0)
CCtsp_generate_edges (277700)
Time for Add edges: 12.74 seconds (598.21 total in 26 calls)
0 edges added, penalty -0.000000
New lower bound: 142337829.789410
Time for Full edge check: 12.75 seconds (193.43 total in 10 calls)
Time for Cutting Loop: 5120.45 seconds (45460.15 total in 5 calls)
Number of outside rounds: 2
CCtsp_x_greedy_tour ...
85721 edges in x-tour
tour length: 152672150.00 (0.04 seconds)
Built CCkdtree: 0.06 (seconds)
..................................................................................... 237015 edges
Quad Nearest added 237015 edges (1.15 seconds)
Edgegen total edges: 237015 (1.21 seconds)
x-heuristic lk gives: 143529055.00
Time for Lin-Kernighan: 4.38 seconds (4.38 total in 1 calls)
Final lower bound 142337829.789410, upper bound 142383704.000000
Exact Price Time: 1568.33 seconds
Exact lower bound: 142337829.789398
DIFF: 0.000012
Time for Total: 47032.86 seconds (47032.86 total in 1 calls)
Final LP has 94381 rows, 169126 columns, 956289 nonzeros
Total Running Time: 47035.35 (seconds)
Final Pool: 203575 cuts
Final Domino Pool: 5642 cuts