Comparison of cost vs quality for a random cost matrix

Eric P. Hanson

We will use TravelingSalesmanExact to compute the exact cost and compare to the estimated best costs found by TravelingSalesmanHeuristics with various settings of quality. First we load the packages:

using TravelingSalesmanExact, GLPK
using TravelingSalesmanHeuristics
using TravelingSalesmanExact: ATT, euclidean_distance
using TravelingSalesmanBenchmarks
using Plots
using Random
gr(fmt=:svg)

Plots.GRBackend()

Then we generate a cost matrix uniformly at random, although with a fixed seed for reproducibility:

Random.seed!(147);
N = 50
cost = 100*rand(N, N)

50×50 Array{Float64,2}:
 92.9412   97.6414  32.217    86.4638    …  85.905    50.9177   87.5374 
 16.8919   31.2935  61.9925   93.9285       54.9582   37.9801   74.0727 
 34.334    62.0831  20.855    34.3777       65.2165    3.91999   3.22986
 15.107    61.6168  65.792     0.950158     72.3499   90.0393   54.7066 
  5.65037  68.351   82.1077   38.6359       89.8377    8.37952  47.6852 
 52.2859   31.0052  61.1977   95.0863    …  88.76     68.8905   83.288  
 15.6986   37.5086  42.5669   12.6588       76.9531   38.9794   30.1938 
 16.131    34.7992  93.5873   13.1079       86.7407   28.1613   69.3284 
 56.5307   40.7898  51.753    38.1677       85.682    33.2229   23.541  
 16.7755   88.3319  37.6494   67.0836       62.2611   43.9527   26.1514 
  ⋮                                      ⋱                              
 31.7354   49.0882  79.5527   74.6803       50.7704   37.1903   87.3949 
 69.3424   80.1918   8.04794  80.2869       48.1405   69.3252   26.7735 
  5.82745  83.2745  66.8109   57.2866       47.338     5.08831  45.0234 
 77.5612   72.5688  72.744    29.2251       94.5893    3.17972  18.5553 
 81.1714   61.2879  12.8567   79.9945    …   7.32883  39.8493    1.87466
 39.0075   41.2051  28.5807   82.5032       85.4122   15.3504   22.7234 
 28.1054   17.1756  26.5355    4.01906      76.4092   63.396    21.5952 
 61.5427   82.1747  45.0924    5.11499      22.9342   96.6566   12.8664 
 38.6427   19.5436  37.8428   45.3175       57.7158   53.0632   12.7643

This is a very odd cost matrix for a TSP problem, since e.g. the diagonal is non-zero.

Now we will compute an optimal tour and cost, and plot these versus those found by the tsp_solve function of TravelingSalesmanHeuristics.

t_exact, c_exact = get_optimal_tour(cost, with_optimizer(GLPK.Optimizer))

c(q) = solve_tsp(cost; quality_factor = q)[2]

qs = range(10, stop = 100, step = 10)

plot(qs, c, xlabel="quality", ylabel="Cost", label="solve_tsp 1", title="random cost matrix")
for j = 2:5
    plot!(qs, c, label="solve_tsp $j")
end
hline!([c_exact], label="Exact cost")

We've run tsp_solve five times for each quality, since the cost will vary from run to run due to the randomness of the heuristics. It seems like the heuristics do not perform well, but I believe that is due to the pathological cost matrix, which likely violates some assumptions of the heuristics.

Appendix

These benchmarks are a part of the TravelingSalesmanBenchmarks.jl repository, found at: https://github.com/ericphanson/TravelingSalesmanBenchmarks.jl, based on the weave branch of DiffEqBenchmarks.

To locally run this tutorial, do the following commands:

using TravelingSalesmanBenchmarks
TravelingSalesmanBenchmarks.weave_file("random_50_cost_vs_quality.jmd")

Computer Information:

Julia Version 1.1.0
Commit 80516ca202 (2019-01-21 21:24 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin14.5.0)
  CPU: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, broadwell)
Environment:
  JULIA_EDITOR = "/Applications/Visual Studio Code.app/Contents/Frameworks/Code Helper.app/Contents/MacOS/Code Helper"

Package Information:

Status: `/Users/eh540/Dropbox (Personal)/LinkedFolders/Julia/dev/TravelingSalesmanBenchmarks/Project.toml`
[a93c6f00-e57d-5684-b7b6-d8193f3e46c0] DataFrames 0.17.1
[60bf3e95-4087-53dc-ae20-288a0d20c6a6] GLPK 0.9.1
[2e9cd046-0924-5485-92f1-d5272153d98b] Gurobi 0.6.0
[7073ff75-c697-5162-941a-fcdaad2a7d2a] IJulia 1.18.1
[91a5bcdd-55d7-5caf-9e0b-520d859cae80] Plots 0.24.0
[737fac7d-4440-55ef-927e-002196e95561] TravelingSalesmanExact 0.3.2
[8c8f4381-2cdd-507c-846c-be2bcff6f45f] TravelingSalesmanHeuristics 0.3.1
[44d3d7a6-8a23-5bf8-98c5-b353f8df5ec9] Weave 0.9.0
[ddb6d928-2868-570f-bddf-ab3f9cf99eb6] YAML 0.3.2
[b77e0a4c-d291-57a0-90e8-8db25a27a240] InteractiveUtils 
[d6f4376e-aef5-505a-96c1-9c027394607a] Markdown 
[44cfe95a-1eb2-52ea-b672-e2afdf69b78f] Pkg 
[de0858da-6303-5e67-8744-51eddeeeb8d7] Printf 
[9a3f8284-a2c9-5f02-9a11-845980a1fd5c] Random 
[10745b16-79ce-11e8-11f9-7d13ad32a3b2] Statistics

Published from random_50_cost_vs_quality.jmd using Weave.jl on 2019-04-22.