To solve kj37859, we began with a short run of LKH, resulting in a tour of length 28237074. Output from the run is recorded in kj37859.lkh.log. The total time was 3.6 hours on a single core of an Intel Xeon E5-2697 v2 @ 2.70GHz server. The run was made with standard settings of LKH; no effort was made to tune the parameters to the large 3D instance.
While LKH was running, we also made an initial cutting-plane run with Concorde. This produced an LP relaxation providing a lower bound of 28235208 on the length of any tour. The output of the run is recorded in kj37859.concorde.0.log. The Concorde time was 4.2 hours on a single core of the same Intel processor.
We then made a second cutting-plane run, starting with the initial LP relaxation and using the 28237074 value to measure progress in the LP bound (to determine when to terminate certain of the cutting-plane routines). This produced a new LP relaxation with a lower bound of 28235243. You can see the output in kj37859.concorde.1.log. This second run used another 11.9 hours on a single core of the Intel processor.
The gap between the length of the LKH tour and the value of the LP relaxation was small enough to allow us to apply Concorde's standard branch-and-cut process. This search produced an optimal tour in approximately 10 hours, running in parallel on a network of 288 Intel Xeon CPU E5-2620 0 @ 2.00GHz cores and 16 Intel Xeon E5-2697 v2 @ 2.70GHz cores. The output of the controlling process is recorded in kj37859.bnb.log.
The branch-and-cut run processed 10,641 subproblems. A drawing of the search tree is given in kj37859_tree.pdf. The optimal tour length is 28235453.