TravelingSalesmanExact.jl
TravelingSalesmanExact.ATT
TravelingSalesmanExact.euclidean_distance
TravelingSalesmanExact.find_cycle
TravelingSalesmanExact.get_ATT48_cities
TravelingSalesmanExact.get_cycles
TravelingSalesmanExact.get_default_optimizer
TravelingSalesmanExact.get_optimal_tour
TravelingSalesmanExact.plot_cities
TravelingSalesmanExact.plot_tour
TravelingSalesmanExact.remove_cycles!
TravelingSalesmanExact.set_default_optimizer!
TravelingSalesmanExact.simple_parse_tsp
Example
julia> using TravelingSalesmanExact, HiGHS
julia> set_default_optimizer!(HiGHS.Optimizer)
HiGHS.Optimizer
julia> cities = TravelingSalesmanExact.get_ATT48_cities();
julia> distance = TravelingSalesmanExact.ATT;
julia> tour, cost = get_optimal_tour(cities; distance, verbose=true, slow=true)
([5, 42, 24, 10, 45, 35, 4, 26, 2, 29 … 30, 36, 46, 33, 20, 47, 21, 32, 39, 48], 10628.0)
API Reference
TravelingSalesmanExact.ATT
— MethodATT(city1, city2)
The ATT
distance measure as specified in TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf.
TravelingSalesmanExact.euclidean_distance
— Methodeuclidean_distance(city1, city2)
The usual Euclidean distance measure.
TravelingSalesmanExact.find_cycle
— Functionfind_cycle(perm_matrix, starting_ind)
Returns the cycle in the permutation described by perm_matrix
which includes starting_ind
.
TravelingSalesmanExact.get_ATT48_cities
— Methodget_ATT48_cities() -> Vector{Vector{Int}}
A simple helper function to get the problem data for the ATT48 TSPLIB problem.
Example
julia> using TravelingSalesmanExact, HiGHS
julia> cities = TravelingSalesmanExact.get_ATT48_cities()
48-element Vector{Vector{Float64}}:
[6734.0, 1453.0]
[2233.0, 10.0]
[5530.0, 1424.0]
[401.0, 841.0]
[3082.0, 1644.0]
[7608.0, 4458.0]
[7573.0, 3716.0]
[7265.0, 1268.0]
[6898.0, 1885.0]
[1112.0, 2049.0]
⋮
[6271.0, 2135.0]
[4985.0, 140.0]
[1916.0, 1569.0]
[7280.0, 4899.0]
[7509.0, 3239.0]
[10.0, 2676.0]
[6807.0, 2993.0]
[5185.0, 3258.0]
[3023.0, 1942.0]
julia> get_optimal_tour(cities, HiGHS.Optimizer, distance = TravelingSalesmanExact.ATT)
([5, 42, 24, 10, 45, 35, 4, 26, 2, 29 … 30, 36, 46, 33, 20, 47, 21, 32, 39, 48], 10628.0)
TravelingSalesmanExact.get_cycles
— Methodget_cycles(perm_matrix)
Returns a list of cycles from the permutation described by perm_matrix
.
TravelingSalesmanExact.get_default_optimizer
— Methodget_default_optimizer()
Gets the default optimizer, which is set by set_default_optimizer
.
TravelingSalesmanExact.get_optimal_tour
— Functionget_optimal_tour(
cities::AbstractVector,
optimizer = get_default_optimizer();
distance = euclidean_distance,
kwargs...
)
get_optimal_tour(
cost::AbstractMatrix
optimizer = get_default_optimizer();
kwargs...
)
Solves the travelling salesman problem for a list of cities using JuMP by formulating a MILP using the Dantzig-Fulkerson-Johnson formulation and adaptively adding constraints to disallow non-maximal cycles. Returns an optimal tour and the cost of the optimal path. Optionally specify a distance metric.
The second argument is mandatory if a default optimizer has not been set (via set_default_optimizer
). This argument should be a function which creates an optimizer, e.g.
get_optimal_tour(cities, HiGHS.Optimizer)
There are five boolean optional keyword arguments:
verbose
(default: false) indicates whether or not to print lots of information as the algorithm proceeds.symmetric
indicates whether or not the cost matrix is symmetric. By default,issymmetric
is used to check.lazy_constraints
indicates whether lazy constraints should be used (which requires a compatible solver, like GLPK).slow
artificially sleeps after each solve to slow down the output for visualization purposes. Only takes affect ifverbose==true
.silent_optimizer
callsJuMP.set_silent
on the resulting model to prevent the optimizer from emitting logging information.heuristic_warmstart=true
: whether or not to warmstart the solves using a heuristic solution. Not supported by all solvers.
Example
julia> using TravelingSalesmanExact, HiGHS, LinearAlgebra
julia> set_default_optimizer!(HiGHS.Optimizer)
HiGHS.Optimizer
julia> cities = [[0, 0], [0, 1], [1, 1], [1, 0]]
4-element Vector{Vector{Int64}}:
[0, 0]
[0, 1]
[1, 1]
[1, 0]
julia> tour, cost = get_optimal_tour(cities)
([4, 1, 2, 3], 4.0)
julia> cost_matrix = [norm(cities[i] - cities[j]) for i = 1:4, j = 1:4]
4×4 Matrix{Float64}:
0.0 1.0 1.41421 1.0
1.0 0.0 1.0 1.41421
1.41421 1.0 0.0 1.0
1.0 1.41421 1.0 0.0
julia> tour, cost = get_optimal_tour(cost_matrix)
([4, 1, 2, 3], 4.0)
TravelingSalesmanExact.plot_cities
— Methodplot_cities(cities)
Uses UnicodePlots
's lineplot
to make a plot of the tour of the cities in cities
, in order (including going from the last city back to the first).
TravelingSalesmanExact.plot_tour
— Methodshow_tour(cities, perm_matrix)
Show a plot of the tour described by perm_matrix
of the cities in the vector cities
.
TravelingSalesmanExact.remove_cycles!
— Methodremove_cycles!(model, solutions)
Find the (non-maximal-length) cycles in the current solutions solutions
and add constraints to the JuMP model to disallow them. Returns the number of cycles found.
TravelingSalesmanExact.set_default_optimizer!
— Methodset_default_optimizer(O)
Sets the default optimizer. For example,
using HiGHS
set_default_optimizer(HiGHS.Optimizer)
TravelingSalesmanExact.simple_parse_tsp
— Methodsimple_parse_tsp(filename; verbose = true)
Try to parse the ".tsp" file given by filename
. Very simple implementation just to be able to test the optimization; may break on other files. Returns a list of cities for use in get_optimal_tour
.