Comparison of cost vs quality for `att48.tsp` dataset

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
gr(fmt=:svg)
repo_directory = TravelingSalesmanBenchmarks.repo_directory;
data_directory = joinpath(repo_directory, "data");

Then load the dataset

cities = simple_parse_tsp(joinpath(data_directory, "att48.tsp"), verbose = false)
N = length(cities)
cost = [ ATT(cities[i], cities[j]) for i=1:N, j=1:N ]

48×48 Array{Int64,2}:
    0  1495   381  2012  1157   990  …  1104   616  2162   488   753  1184
 1495     0  1135   637   583  2207     2223  1957  1098  1727  1388   661
  381  1135     0  1633   778  1163     1231   850  1790   640   591   810
 2012   637  1633     0   886  2550     2526  2373   594  2138  1695   900
 1157   583   778   886     0  1686     1680  1489  1025  1253   839    97
  990  2207  1163  2550  1686     0  …   174   387  2468   528   856  1654
  764  2056   971  2444  1565   235      386   153  2415   334   769  1545
  178  1641   551  2175  1329  1015     1149   629  2338   565   911  1359
  147  1590   457  2081  1210   845      961   470  2193   352   695  1226
 1788   736  1412   444   636  2191     2149  2058   401  1826  1344   606
    ⋮                             ⋮  ⋱                       ⋮            
  261  1443   325  1901  1021   848      931   525  1988   320   495  1029
  692   872   442  1467   768  1598  …  1671  1264  1766  1071   989   843
 1525   504  1144   532   370  2019     1997  1846   698  1611  1164   370
 1104  2223  1231  2526  1680   174        0   530  2405   622   842  1640
  616  1957   850  2373  1489   387      530     0  2379   236   735  1477
 2162  1098  1790   594  1025  2468     2405  2379     0  2152  1647   981
  488  1727   640  2138  1253   528  …   622   236  2152     0   520  1242
  753  1388   591  1695   839   856      842   735  1647   520     0   801
 1184   661   810   900    97  1654     1640  1477   981  1242   801     0

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="att48.tsp")
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.

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("att48_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