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