Comparison of cost vs quality for a random symmetric 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 by taking a matrix uniformly at random and symmetrizing it, with a fixed seed for reproducibility:

Random.seed!(758)
N = 50
cost = 100*rand(N, N)
cost = (cost + transpose(cost) )/2

50×50 Array{Float64,2}:
 22.8248  41.3445   53.5929  39.1792  35.2913  …  47.2814   44.6921   63.09
45
 41.3445  13.1004   73.5235  55.3009  21.3577      7.21117   7.95262  43.62
36
 53.5929  73.5235   94.3781  15.3588  32.0469     22.1608   32.8762   53.04
74
 39.1792  55.3009   15.3588   6.4889  57.6645     23.1055   45.7339   48.58
97
 35.2913  21.3577   32.0469  57.6645  35.839      26.109    37.426    48.69
61
 35.9583  55.201    39.093   38.341   78.4554  …  81.0471   67.1443   61.32
85
 46.3519  62.3843   62.3551  71.7588  57.538      43.3942   31.7907   56.28
28
 28.4214  66.4843   12.7711  60.2753  69.8672     55.1447   64.1496   34.32
35
 78.6491  39.8221   63.9344  23.893   64.0864     51.8869   83.0205   76.81
73
 13.229   59.8764   51.2916   8.1257  45.1743     33.4251   70.3754   48.01
71
  ⋮                                            ⋱                           
  
 41.5839  39.6921   64.83    68.6766  63.3925     58.7033   77.5336   14.92
28
 81.0534  50.161    28.101   62.3008  64.0195     43.4937   48.3701   52.13
26
  5.4622  79.1732   11.1337  57.0497  44.1113     49.1062   64.2019   34.71
3 
 21.392   62.2546   66.2069  56.8905  26.1311     14.1168   79.7081   24.71
7 
 32.5348  43.5087   50.4695  37.2779  50.1287  …  73.0339   15.687    42.78
62
 42.6627  36.5543   47.0154  67.1887  73.7858     42.773    19.8238   76.37
81
 47.2814   7.21117  22.1608  23.1055  26.109      97.7158   55.2536   35.30
3 
 44.6921   7.95262  32.8762  45.7339  37.426      55.2536   80.0741   44.91
38
 63.0945  43.6236   53.0474  48.5897  48.6961     35.303    44.9138   60.74
65

Note that this is a very odd cost matrix for a TSP problem, since e.g. the diagonal is non-zero, although it is symmetric.

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 symmetric 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 that 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_symmetric_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