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

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.