Robert Bosch, February 2009
mona-lisa100K.tsp
New!  $100 Prize Offered

In February 2009, Robert Bosch created a 100,000-city instance of the traveling salesman problem (TSP) that provides a representation of Leonardo da Vinci's Mona Lisa as a continuous-line drawing. Techniques for developing such point sets have evolved over the past several years through work of Bosch and Craig Kaplan.

An optimal solution to the 100,000-city Mona Lisa instance would set a new world record for the TSP. If you have ideas for producing good tours or for showing that a solution is optimal, this is a very nice challenge problem! I would be happy to report any computational results you obtain on this example. The data set in TSPLIB format is given in the file

mona-lisa100K.tsp

The following papers describe various aspects of the mathematics behind the selection of city locations for the Mona Lisa TSP.

Pretty examples of other TSP drawings can be found on Robert Bosch's TSP Art page and on the page of Craig Kaplan.

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

Tour:  5,757,191     Bound:  5,757,029     Gap:  166 (0.0028%)

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 November 4, 2009, with the Concorde code.

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


Computation Log

November 5, 2009:  The cutting planes gathered during the April 16 truncated branch-and-cut run were used to further improve the linear-programming (LP) relaxation for the Mona Lisa TSP. The resulting LP value actually went above the bound from the branching tree, reaching an LP bound of 5757028.3. This is good news, since we can now start a new branch-and-cut run from this LP. The new LP was created by repeatedly applying the new cuts via a procedure that modifies them to better fit the current LP relaxation (a "tightening" procedure).

August 1, 2009:  The truncated branch-and-cut run was terminated on August 1 following a power outage at Georgia Tech. The run could be restarted from where it left off, but after 116 days it is a good stopping point. The search tree grew to 130 active subproblems (and 299 nodes in the tree). The worst of the LP bounds for the subproblems is 5057024.55. So the new overall lower bound is 5057025!

May 16, 2009:  The truncated branch-and-cut search that was started with the April 7 LP relaxation continues to run. After 40 days, the search has taken sixteen branching steps. The worst of the LP bounds for the seventeen subproblems is 5757004.76, yielding an overall lower bound of 5,757,005. The run is being carried out in parallel on 13 processor cores. A drawing of the search tree is given here. In the drawing, the height of a node gives the LP bound of the corresponding subproblem; the red nodes represent subproblems that have not yet been processed with additional cutting planes and the magenta nodes are ready to be split into further subproblems.

April 16, 2009:  A new truncated branch-and-cut search was started with the April 7 LP relaxation. An artificial upper bound of 5,757,057 was used this time. After 10 days, the search has taken two branching steps, creating a total of three subproblems. The LP bounds for the three problems are currently 5756994.17, 5756994.02, and 5756993.02. Since we know that all tours have integer length, an overall lower bound of 5,756,994 has been established. (This is the worst of the three LP bounds rounded up to the next integer.) The three subproblems continue to run, using three processor cores.

April 7, 2009:  A main goal of the March 30 truncated branch-and-cut run was to gather cutting planes that can be used to improve the linear-programming (LP) relaxation for the Mona Lisa TSP. Using the March 30 cutting planes and starting with the March 4 LP relaxation, Concorde improved the LP bound to 5,756,982. This is an improvement of 47 units over the March 4 LP and it is nearly the value of the bound obtained in the truncated branch-and-cut run. We can therefore expect a further improvement in the bound by again running a branch-and-cut search. The Concorde options used in the run were -mC48 -Z3. The log file can be found here.

March 30, 2009:  The lower bound was improved using a short branch-and-cut run with Concorde and the artificial upper bound of T = 5,756,985. Using the possibly invalid upper bound T allows Concorde to eliminate many variables from the LP relaxation, obtaining a problem that can be managed in a branch-and-cut search. ("Possibly invalid" here means that we do not actually know a tour of length T.) This type of run can establish a lower bound of up to T, but no higher. In this particular case, splitting the problem into two subproblems and applying Concorde established the bound of 5,765,985. This result gives a gap of 206 (0.0358%) to the tour of Yuichi Nagata. The Concorde run used 25.3 days of computing time on a 2.66 GHz Intel Xeon 5355 processor.

March 17, 2009:  Yuichi Nagata has improved the best known tour result by 8 units! His solution was found via series of computations with a genetic algorithm that he has designed. The new record tour has length 5,757,191 and it is given in the file: monalisa_5757191.tour.

March 16, 2009:  Keld Helsgaun improved his previous best tour by a single unit, using a stronger form of LKH's 10-opt moves. The new tour of length 5,757,199 is given in the file: monalisa_5757199.tour.

March 8, 2009:  Keld Helsgaun found another improvment, using 10-opt submoves on his March 7 tour. His new tour has length 5,757,200, improving the previous best known result by 3 units. The tour in TSPLIB format is given in the file: monalisa_5757200.tour.

March 7, 2009:  Keld Helsgaun improved the tour again with LKH, obtaining an improvement of 2 units from his previous tour (so 1 unit better than the tour obtained by Dong et al.). The new tour has length 5,757,203, giving a gap of 268 to the Concorde bound. Helsgaun's tour in TSPLIB format is given in the file: monalisa_5757203.tour.

March 6, 2009:  Changxing Dong, Christian Ernst, Gerold Jaeger, Dirk Richter and Paul Molitor used Helsgaun's (March 4) tour as a starting point and improved the tour by 1 unit. The new tour of length 5,757,204 is given in the file: monalisa_5757204.tour.

March 4, 2009:  Running Concorde, starting with the previous linear-programming relaxation, and now with the option -mC44 -Z3, improved the lower bound by 66 units to 5,756,935. The -Z3 flags turn on the use of domino-partiy constraints. The gap to the best known tour is now 270 (0.00469%). The log file for the Concorde run can be found here.

March 2, 2009:  Keld Helsgaun found a new record tour, improving the previous best known result by 36 units! The new tour has length 5,757,205, giving a gap of only 336 units (0.00587%) to the Concorde bound from February 24. Helsgaun found his tour by using parallel LKH to obtain tours of length 5,757,264 and 5,757,269. The common edges in these two tours and the previous 5,757,245 tour were fixed, and the resulting smaller instance was run with high-order k-opt submoves. Helsgaun's tour in TSPLIB format is given in the file: monalisa_5757205.tour.

March 2, 2009:  Changxing Dong, Christian Ernst, Gerold Jaeger, Dirk Richter and Paul Molitor used a combination of Karp partitioning and LKH-2 to improve Helsgaun's February 26 tour by 4 units (using Helsgaun's tour as a starting point in their run). The tour of length 5,757,241 is 372 units (0.00646%) longer than the Concorde bound. The new tour in TSPLIB format is given in the file: monalisa_5757241.tour.

February 26, 2009:  Keld Helsgaun found a new best known tour using a parallel version of LKH. The tour of length 5,757,245 is only 376 units (0.00653%) longer than the Concorde bound established on February 24. Helsgaun's tour in TSPLIB format is given in the file: monalisa_5757245.tour.

February 26, 2009:  Keld Helsgaun reports that a 1,000-trial run of LKH-2 with 5-opt moves found a tour of length 5,758,239, while a single trial run with 8-opt moves found a tour of length 5,757,795. Log files for the two LKH-2 runs can be found here-5opt and here-8opt.

February 24, 2009:  A second run of Concorde, starting with the linear-programming relaxation produced in the February 22 run, and now with the option -mC48, produced a lower bound of 5,756,869. This gives a gap of 1,962 (0.0341%) to the LKH tour. The log file for the Concorde run can be found here.

February 23, 2009:  An initial LKH run found a tour of length 5,758,831 using 1,000 trials. The tour in TSPLIB format is given in the file: monalisa_5758831.tour. The log file for the LKH run can be found here.

February 22, 2009:  Running Concorde with the -mC32 option produced a lower bound of 5,756,619, thus no tour can be shorter than this amount. The log file for the Concorde run can be found here.