Mona Lisa TSP

The current best known results for the Mona Lisa TSP are:

Tour: 5,757,191 Bound: 5,757,080 Gap: 111 (0.0019%)

The tour was found on March 17, 2009, by Yuichi Nagata. The bound gives a value
B such that no tour has length less than B; this bound was found on February 16,
2012, with the Concorde code. The Gap number is the gap in our knowledge, that
is, the difference between the length of the tour and the value of the bound.

It has been over two years since Yuichi Nagata produced the best-known tour. To
help perk up interest in searching for an even better solution, we are offering
a $1,000 prize to the first person to find a tour shorter than 5,757,191.

Computation Log

February 16, 2012: GAP=111. A truncated branch-and-cut search, using an an
artificial uppper bound of 5757080 and the LP from January 21, completed in 5.6
CPU years and 5,073 search nodes. The run improved the gap by 8 units.

January 21, 2012: LP = 5757067.2. Repeated runs of Concorde's cutting-plane
routines, equipped with a large pool of cuts obtained in the branch-and-cut
search begun on July 7, 2011, increased the LP bound by 12 units over the
previous best obtained on July 7, 2011. The increase is small, given the amount
of computation involved, but it does amount to closing roughly 9% of the
remaining gap between the LP bound and the best known tour. The LP solution
vector is given in the file mona.4zsub.x and a drawing of the solution is given
in mona.5zsub.pdf. We need better separation routines!

Sumber:
http://www.tsp.gatech.edu/data/ml/monalisa.html