Home

# TravelingSalesmanExact.jl

``````get_optimal_tour(
cost::AbstractMatrix,
with_optimizer = get_default_optimizer();
verbose = false,
symmetric = issymmetric(cost),
)``````

Solves the travelling salesman problem for a square cost matrix 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.

The second argument is mandatory if a default optimizer has not been set (via `set_default_optimizer`). This argument should be the result of a call to `JuMP.with_optimizer`, e.g.

``get_optimal_tour(cities, with_optimizer(GLPK.Optimizer))``
source
``````get_optimal_tour(
cities::AbstractVector,
with_optimizer = get_default_optimizer();
verbose = false,
distance = euclidean_distance,
symmetric = true,
)``````

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 the result of a call to `JuMP.with_optimizer`, e.g.

``get_optimal_tour(cities, with_optimizer(GLPK.Optimizer))``
source
``plot_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).

source
``set_default_optimizer(O::OptimizerFactory)``

Sets the default optimizer. For example,

``````using GLPK
set_default_optimizer(with_optimizer(GLPK.Optimizer))``````
source
``simple_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`.

source
``ATT(city1, city2)``

The `ATT` distance measure as specified in TSPLIB: https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp95.pdf.

source
``euclidean_distance(city1, city2)``

The usual Euclidean distance measure.

source
``find_cycle(perm_matrix, starting_ind)``

Returns the cycle in the permutation described by `perm_matrix` which includes `starting_ind`.

source
``get_cycles(perm_matrix)``

Returns a list of cycles from the permutation described by `perm_matrix`.

source
``get_default_optimizer()``

Gets the default optimizer, which is set by `set_default_optimizer`.

source
``show_tour(cities, perm_matrix)``

Show a plot of the tour described by `perm_matrix` of the cities in the vector `cities`.

source
``remove_cycles!(model, tour_matrix)``

Find the (non-maximal-length) cycles in the current solution `tour_matrix` and add constraints to the JuMP model to disallow them. Returns the number of cycles found.

source