Combinatorial Optimization Functions

In the following we will show several power examples of the TSP functions in JVMTools, and we’ll include the solutions of the modified Kruskal algorithm for the minimum spanning tree problem along with the TSP solutions, as the modified Kruskal algorithm runs extremely fast and the depictions of the solutions help us understand the TSP solutions.

We will use the coordinates of several cities, this data is built in Mathematica. We will be using the ConcurrentPostOpt option throughout, as it provides the best run time/quality ratio ("cost/benefit ratio"). In some cases we will also use the ConcurrentPostOptSequential method if further improvement of the solution appears possible. We will try to pick interesting geographies/shapes to illustrate the solutions.

We will not mention it every time explicitly, but note that ConcurrentPostOpt, ConcurrentPostOptSequential and the MAOS algorithm all operate in a concurrent manner, making full use of the parallel cores on the user’s hardware by using the concurrency framework of the JVM.

First we define a distance function that computes the great circle distance in statute miles, given the latitude and longitude coordinates of a given city.

The following are a minimum spanning tree and a Travelling Salesman Tour of all large cities in the United States (excluding Alaska and Hawaii).

This is the minimum spanning tree:

This is the travelling salesman solution.

The length of the optimal solution is 14347, so JVMTools' ConcurrentPostOpt method produced a solution in 2 seconds that is only 1.6% above optimal.

By increasing the problem size the runtimes also get larger very quickly. The following are a minimum spanning tree and a Travelling Salesman Tour of all cities in the United States with city populations larger than 35,000 (excluding Alaska and Hawaii). This means 1,156 cities. These could not be solved with Mathematica's FindShortestTour[] function at all due to problem size.

This is the minimum spanning tree:

This is the travelling salesman solution:

The optimal tour has a solution of length 23790. The solution produced by JVMTools' ConcurrentPostOpt is only 3.5% above optimal.

However, the solution can be improved further with sequential application of post-opt methods, at the expense of longer running times:

This solution is 2.1% above optimal, but it required 35 minutes computation time.

MAOS finds 23794.4 (that is 0.018% above optimal) in 34 seconds ...

... and 23797.6 (0.032% above optimal) in 8 seconds ...

Here we increase the problem size further. Here we compute a minimum spanning tree and a Travelling Salesman Tour of all cities in the United States with city populations larger than 15,000 (excluding Alaska and Hawaii). This means 2,827 cities, and JVMTools solves the minimum spanning tree problem in less than 2 minutes and the Travelling Salesman Tour (using MAOS) in 2 minutes.

This is the minimum spanning tree:

The optimal solution was not determined, but it is assumed that the MAOS solution is less than 1% above optimal.

The following example shows the minimum spanning tree and the Travelling Salesman Tour solution of all cities in Japan.

The minimum spanning tree solution :

The TSP solution:

The length of the optimal solution is 8596, so JVMTools' ConcurrentPostOpt is only 2.43% above optimal.

With the option ConcurrentPostOptSequential the solution can be improved even further, however the running time increases substantially due to the ChainInsertion method used internally:

This evaluation took about 70 minutes. The solution is only 1.01% above optimal.

MAOS finds the optimal solution in less than 5 seconds. Note that there are slight inaccuracies due to the fact that the function was called with the EUC_2D 2-dimensional Euclidean norm as distance function, although for geomatric latitude/longitude coordinates the correct norm to use would be the great circle distance (see above).

The following example shows the minimum spanning tree and the Travelling Salesman Tour solution of all cities in Chile.

The minimum spanning tree solution :

The TSP solution:

The length of the optimal solution is 9051.63, so JVMTools' ConcurrentPostOpt is only 0.7% above optimal.

MAOS finds the optimal solution in less than 1 second:

The following example shows the minimum spanning tree and the Travelling Salesman Tour solution of all cities in Ecuador.

The minimum spanning tree solution :

The TSP solution:

The length of the optimal solution is 2908, so JVMTools' ConcurrentPostOpt is 2.8% above optimal.

We try the sequential method:

This solution is 2.1% above optimal.

Occasionally for small problems such as this (113 cities) a random initial tour provides the best starting conditions for the post-opt methods. For example, with the random initial tour

we can obtain:

which is 0.7% above optimal with a single method call and even

with sequential post-opt method calls, which provides a solution that is 0.4% above optimal.

Of course, there is never a guarantee that random initial tours result in very good solutions, and for larger problems random initial tours are always inferior.

MAOS finds the optimal solution in 1/5 of a second:

For the following examples we have to modify the graphics function a bit, as Mathematica has no maps for the US states:

The following are the minimum spanning tree and the Travelling Salesman Tour of all cities in Illinois.

The optimal solution has a length of 5895. JVMTools' ConcurrentPostOpt method produced a solution that is 3% above optimal.

We try the sequential method:

This solution is 2.2% above optimal, but it needed 38 minutes to compute.

MAOS needs 7 seconds to compute the optimal solution. Again note that there are slight inaccuracies due to the fact that the Euclidean norm and rounding the next integer produces slight different solutions than the great circle distance norm.

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in Maine.

The optimal solution has a length of 2873. JavaTool's ConcurrentPostOpt method is only 0.4% above optimal.

MAOS computes 2879 (that is 0.2% above optimal) in less than 2 seconds.

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in California.

The optimal solution has a length of 6265. JVMTools' ConcurrentPostOpt method is 3.3% above optimal.

The solution produced by JVMTools' sequential method is 1.5% above optimal, but it needed 91 minutes to compute.

MAOS computes the optimal solution in 8 seconds:

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in New York.

The optimal solution has a length of 6035. JVMTools' ConcurrentPostOpt method is 5.4% above optimal.

This solution is 1.2% above optimal, but it took 79 minutes to compute.

MAOS produces the optimal solution in less than 10 seconds:

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in Texas.

The optimal solution has a length of 11436. JVMTools' ConcurrentPostOpt produces a solution that is 3.5% above optimal.

We try the sequential method:

This solution is 3.1% above optimal, however, it took about an hour to compute.

MAOS computes 11436 (that is optimal) in 13 seconds.

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in Hawaii.

The optimal solution has a length of 825. JVMTools' ConcurrentPostOpt produces a solution that is 0.05% above optimal.

MAOS computes the optimal solution in less than half a second:

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in Oklahoma.

The optimal solution has a length of 4572. JVMTools' ConcurrentPostOpt produces a solution that is 3.1% above optimal.

We try the sequential method:

This solution is 2.4% above optimal. It took less than 2 minutes to compute.

MAOS computes the optimal solution less than 5 seconds. Again note slight inaccuracies due to the fact that Euclidean norm is slightly off when great circle distances should be used.

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in Maryland.

The optimal solution has a length of 1289. JVMTools' ConcurrentPostOpt produces a solution that is 3.2% above optimal.

We try the sequential method:

This solution is 2% above optimal. It took less than a minute to compute.

MAOS computes the optimal solution less than 5 seconds.

The following are a minimum spanning tree and the Travelling Salesman Tour of all cities in West Virginia.

The optimal solution has a length of 1706. JVMTools' ConcurrentPostOpt produces a solution that is 2.9% above optimal.

We try the sequential method:

This solution is 0.4% above optimal.

MAOS computes the optimal solution less than a second. Again note slight inaccuracies due to the fact that Euclidean norm is slightly off when great circle distances should be used.

The author is inviting competing implementations in Mathematica or Java or both for large problems at info@lauschkeconsulting.net to challenge the presented performance claims.