TravelingSalesmanExact.jl

TravelingSalesmanExact.get_optimal_tourFunction
get_optimal_tour(
    cost::AbstractMatrix,
    optimizer = get_default_optimizer();
    verbose::Bool = false,
    symmetric::Bool = issymmetric(cost),
    lazy::Bool = true,
)

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 a function which creates an optimizer, e.g.

    get_optimal_tour(cities, GLPK.Optimizer)

There are three boolean optional keyword arguments:

  • verbose indicates whether or not to print lots of information as the algorithm proceeds.
  • symmetric indicates whether or not the cost matrix is symmetric (the default is to check via issymmetric)
  • lazy indicates whether lazy constraints should be used (which requires a compatible solver).
source
TravelingSalesmanExact.get_optimal_tourFunction
get_optimal_tour(
    cities::AbstractVector,
    optimizer = get_default_optimizer();
    verbose = false,
    distance = euclidean_distance,
    symmetric = true,
    lazy_constraints = false,
)

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, GLPK.Optimizer)

There are three boolean optional keyword arguments:

  • verbose indicates whether or not to print lots of information as the algorithm proceeds.
  • symmetric indicates whether or not the distance metric used is symmetric (the default is to assume that it is)
  • lazy_constraints indicates whether lazy constraints should be used (which requires a compatible solver).
source
TravelingSalesmanExact.plot_citiesMethod
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
TravelingSalesmanExact.simple_parse_tspMethod
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
TravelingSalesmanExact.get_ATT48_citiesMethod
get_ATT48_cities() -> Vector{Vector{Int}}

A simple helper function to get the problem data for the ATT48 TSPLIB problem.

Example

using TravelingSalesmanExact, GLPK
cities = TravelingSalesmanExact.get_ATT48_cities()
get_optimal_tour(cities, GLPK.Optimizer, distance = TravelingSalesmanExact.ATT)
source
TravelingSalesmanExact.remove_cycles!Method
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