Packages
fixpoint
0.8.7
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 - 1), fn i -> Variable.new(0..(n - 1), name: "succ_#{i}") end)
## Distance between location i and the one that follows i (i.e., successor)
# dist_succ = Enum.map(0..n - 1, fn i -> Variable.new(Enum.at(distance, i), name: "dist_succ#{i}")
# end)
## 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, distances) 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
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
end