**Step 1:** Sort the constraints of the LP relaxation into the known types of inequalities for the TSP.

Prob ID: 0

Prob Parent ID: -1

Prob Bounds: (5757055.220407, 5758915.000000)

Prob Exact Lowerbound: 5757035.236488

No section f in file.

No section g in file.

No section d in file.

Branch History

Root Node

Done with read_probfile

0 of 13975 cuts failed verification

Distribution of cuts

2504 subtours

8313 combs

10 dirty combs

1970 stars

114 bipartition inequalities

1064 domino parity inequalities

4482 other cuts

Writing non-simple cuts to sav.other

Verification completed (successful) in 1.22 seconds

The "other cuts" group are those delivered by the local-cuts routine that do not fit into the known classes. We must check each of these 4,482 unknown constraints.

**Step 2:** Run a reduction procedure that looks for "edge clones." This will reduce the size of some of the unknown constraints (cuts).

Number of cuts: 4482

Number of edge-clone reductions: 597

Number of non-isomorphic cuts: 4482

Writing clone-reduced cuts to cuts.cloned

Completed in 0.21 seconds

**Step 3:** Run a code to test if some cuts are isomorphic to one another (that is, they have the identical structure but defined on different sets of cities). This can reduce the number of cuts that need to be verified.

Number of cuts: 4482

Number of cuts with no outside node: 0

Number of non-isomorphic cuts: 3923

Writing non-isomorphic cuts to cuts.iso

Completed in 0.23 seconds

We are now down to 3,923 unknown cuts. To verify these we will solve a small TSP for each cut, determining the minimum value a tour can obtain. These values should match the right-hand-side of the inequality.

**Step 4:** Run Held-Karp on each cut, limiting the number of search nodes to 1,000,000. This is done in parallel, using a boss-worker framework.

Completed 3923 cuts in 14758.67 seconds

3380 cuts verified with HK

0 cuts verified with with DFS-tsp

543 cuts failed verification

Saving the remaining 543 cuts to cuts.remain

Held-Karp failed to solve the TSP instances for 543 cuts. These need to be solved using other means.

**Step 5:** Increase the Held-Karp limit to 10,000,000 search nodes.

Completed 543 cuts in 83604.88 seconds

263 cuts verified with HK

0 cuts verified with with DFS-tsp

280 cuts failed verification

Saving the remaining 280 cuts to cuts.remain

This solved about half of the remaining cuts. We are down to 280 unknowns.

**Step 6:** Run a simple depth-first-search branch-and-cut code on each of the remaining cuts, limiting the seach time to 100 seconds per cut.

Completed 280 cuts in 21340.78 seconds

0 cuts verified with HK

144 cuts verified with with DFS-tsp

136 cuts failed verification

Saving the remaining 136 cuts to cuts.remain

**Step 7:** Increase the depth-first-search branch-and-cut time limit to 1,000 seconds per cut.

Completed 136 cuts in 106834.62 seconds

0 cuts verified with HK

48 cuts verified with with DFS-tsp

88 cuts failed verification

Saving the remaining 88 cuts to cuts.remain

**Step 8:** Run Held-Karp with a limit of 1,000,000,000 search nodes per cut.

Completed 88 cuts in 631812.42 seconds

65 cuts verified with HK

0 cuts verified with with DFS-tsp

23 cuts failed verification

Saving the remaining 23 cuts to cuts.remain

**Step 9:** Run depth-first-search branch-and-cut with a 50,000-second limit per cut.

Completed 23 cuts in 916861.17 seconds

0 cuts verified with HK

6 cuts verified with with BFS-tsp

17 cuts failed verification

Saving the remaining 17 cuts to cuts.remain

**Step 10:** Time to bring out the big guns. Use Concorde (with local cuts turned off) to solve the remaining 17 TSPs.

Some of these small TSP instances are nasty for Concorde, but they might be easy for other solution methods. If you want to have a look, this v19.tsp example has only 57 cities any yet gives Concorde (without local cuts) a headache.