Packages
fixpoint
0.8.9
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/examples/tsp.ex
defmodule CPSolver.Examples.TSP do
@doc """
The Traveling Salesman problem.
Given:
- a set of n locations;
- for each pair of locations, a distance between them.
Find the shortest possible route that visits each location exactly once and returns to the origin location.
<a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Wikipedia</a>.
"""
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Model
alias CPSolver.Constraint.Circuit
alias CPSolver.Objective
import CPSolver.Constraint.Factory
## Read and compile data from instance file
def model(data) when is_binary(data) do
{_n, distances} = parse_instance(data)
model(distances)
end
def model(distances) do
n = length(distances)
## successor[i] = j <=> location j follows location i
successors =
Enum.map(0..(n - 2), fn i ->
Variable.new(0..(n - 1), name: "succ_#{i}") end) ++ [Variable.new([0, n-1], name: "succ_#{n - 1}")]
## Element constrains
## For each i, distance between i and it's successor must be in i-row of distance matrix
{dist_succ, element_constraints} =
Enum.map(0..(n - 1), fn i ->
element(Enum.at(distances, i), Enum.at(successors, i))
end)
|> Enum.unzip()
{total_distance, sum_constraint} = sum(dist_succ, name: "total_distance")
Model.new(
successors ++ [total_distance],
[
Circuit.new(successors),
sum_constraint
] ++ element_constraints,
objective: Objective.minimize(total_distance),
extra: %{n: n, distances: distances}
)
end
def check_solution(solution, %{extra: %{distances: distances}} = _model) do
n = length(distances)
successors = Enum.take(solution, n)
## In the solution, total cost follows assignments
total_distance = Enum.at(solution, n)
sum_distances =
successors
|> Enum.with_index()
|> Enum.reduce(0, fn {succ, idx}, acc ->
acc + (Enum.at(distances, idx) |> Enum.at(succ))
end)
total_distance == sum_distances && n == MapSet.new(successors) |> MapSet.size()
end
## solution -> sequence of visits
def to_route(solution, model) do
n = model.extra.n
circuit = Enum.take(solution, n)
Enum.reduce(0..(n - 1), [0], fn _idx, [next | _rest] = acc ->
[Enum.at(circuit, next) | acc]
end)
|> Enum.reverse()
end
def parse_instance(filename) do
filename
|> File.read!()
|> String.split("\n", trim: true)
|> then(fn [n_str | lines] ->
n = String.to_integer(String.trim(n_str))
distances =
lines
|> Enum.take(n)
|> parse_matrix()
{n, distances}
end)
end
defp parse_matrix(lines) do
Enum.map(lines, fn line ->
line
|> String.replace("\t", " ")
|> String.split(" ", trim: true)
|> Enum.map(fn num_str -> String.to_integer(String.trim(num_str)) end)
end)
end
def to_dot(distances) do
n = length(distances)
graph = for i <- 0..n-1, j <- 0..n-1, reduce: Graph.new() do
acc ->
weight = Enum.at(distances, i) |> Enum.at(j)
Graph.add_edge(acc, i, j, weight: weight, label: weight)
end
Graph.to_dot(graph)
end
end