Packages
fixpoint
0.8.49
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
alias CPSolver.Variable.Interface
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search.VariableSelector.FirstFail
import CPSolver.Constraint.Factory
alias CPSolver.Utils.TupleArray
require Logger
@checkmark_symbol "\u2713"
@failure_symbol "\u1D350"
def run(instance, opts \\ []) do
model = model(instance)
opts =
Keyword.merge(
[
search: search(model),
solution_handler: solution_handler(model),
space_threads: 8,
timeout: :timer.minutes(5)
],
opts
)
{:ok, _res} = CPSolver.solve_sync(model, opts)
end
## 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)
# ++ [Variable.new(0, name: "succ_#{n - 1}")]
## Element constraints
## 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)
Model.new(
successors,
[
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)
hamiltonian?(successors) &&
total_distance == sum_distances && n == MapSet.new(successors) |> MapSet.size()
end
def search(%{extra: %{distances: distances, n: n}} = _model) do
tuple_matrix = TupleArray.new(distances)
choose_value_fun = fn %{index: idx} = var ->
domain = Interface.domain(var)
d_values = Domain.to_list(domain)
(idx in 1..n &&
Enum.min_by(d_values, fn dom_idx -> TupleArray.at(tuple_matrix, [idx - 1, dom_idx]) end)) ||
Enum.random(d_values)
end
choose_variable_fun = fn variables ->
{circuit_vars, rest_vars} = Enum.split_with(variables, fn v -> v.index <= n end)
(circuit_vars == [] && FirstFail.select_variable(rest_vars)) ||
difference_between_closest_distances(circuit_vars, tuple_matrix)
end
{choose_variable_fun, choose_value_fun}
# {:input_order, choose_value_fun}
end
def solution_handler(model) do
fn solution ->
solution
|> Enum.at(model.extra.n)
|> tap(fn {_ref, total} ->
ans_str = inspect({"total", total})
(check_solution(
Enum.map(solution, fn {_, val} -> val end),
model
) &&
Logger.warning("#{@checkmark_symbol} #{ans_str}")) ||
Logger.error("#{@failure_symbol} #{ans_str}" <> ": wrong -((")
end)
end
end
## Choose the variable with the maximum difference between closest and second closest distance to its successors
##
defp difference_between_closest_distances(circuit_vars, distances) do
Enum.max_by(circuit_vars, fn %{index: idx} = var ->
dom = Interface.domain(var) |> Domain.to_list()
(MapSet.size(dom) < 2 && 0) ||
dom
|> Enum.map(fn value ->
TupleArray.at(distances, [idx - 1, value])
end)
|> Enum.sort(:desc)
|> then(fn dists -> abs(Enum.at(dists, 1) - hd(dists)) end)
end)
end
## solution -> sequence of visits
def to_route(solution, %{extra: %{n: n}} = _model) do
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 hamiltonian?(sequence) do
{cycle_length, _current} =
Enum.reduce_while(sequence, {1, 0}, fn _succ, {length_acc, succ_acc} = acc ->
next = Enum.at(sequence, succ_acc)
if next == 0 do
{:halt, acc}
else
{:cont, {length_acc + 1, next}}
end
end)
cycle_length == length(sequence)
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