Packages
fixpoint
0.10.1
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/quadratic_assignment.ex
defmodule CPSolver.Examples.QAP do
@doc """
The Quadratic Assignment problem.
Given:
- a set of n facilities;
- a set of n locations;
- for each pair of locations, a distance between them;
- for each pair of facilities, a weight of the edge (e.g., the amount of supplies transported) between them.
Assign all facilities to different locations, such that
the sum of products d(i,j ) * w(i, j)
, where d(i,j) is a distance between locations i and j
and w(i, j) is a weight of edge (i, j)
is minimized.
<a href="https://en.wikipedia.org/wiki/Quadratic_assignment_problem">Wikipedia</a>.
"""
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Variable.Interface
alias CPSolver.Model
alias CPSolver.Constraint.AllDifferent.DC, as: AllDifferent
alias CPSolver.Objective
import CPSolver.Constraint.Factory
import CPSolver.Variable.View.Factory
alias CPSolver.Search.VariableSelector, as: Strategy
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.seconds(30)
],
opts
)
{:ok, _res} = CPSolver.solve(model, opts)
end
## Read and compile data from instance file
def model(data) when is_binary(data) do
{_n, distances, weights} = parse_instance(data)
model(distances, weights)
end
def model(distances, weights) do
## TODO: for now we are forced to use 0..n-1 for domains of assignment vars,
## as they will represent 0-based indices (i.e., x and y args) in element2d constraint.
## Not a big deal, but maybe think of supplying the index base for element2d as an option
##
## Note: we assume the distance and weight matrices are symmetrical,
## i.e., distances[i, j] = distances[j, i] and weights[i, j] == weights[j, i]
##
n = length(distances)
assignments =
Enum.map(0..(n - 1), fn i -> Variable.new(0..(n - 1), name: "location_#{i}") end)
## Build "weighted distance" views and element2d constraints
{weighted_distances, element2d_constraints} =
for i <- 0..(n - 2), j <- (i + 1)..(n - 1), reduce: {[], []} do
{weighted_distances_acc, constraints_acc} = acc ->
weight = Enum.at(weights, i) |> Enum.at(j)
if weight == 0 do
acc
else
{z, element2d_constraint} =
element2d(distances, Enum.at(assignments, i), Enum.at(assignments, j))
w_distance = mul(z, weight)
{[w_distance | weighted_distances_acc], [element2d_constraint | constraints_acc]}
end
end
{total_cost, sum_constraint} = sum(weighted_distances)
Model.new(
assignments,
[
AllDifferent.new(assignments),
sum_constraint
] ++ element2d_constraints,
objective: Objective.minimize(total_cost),
extra: %{
n: n,
distances: distances,
weights: weights,
total_cost_var_id: Interface.id(total_cost)
}
)
end
def search(model) do
_location_var_names =
Enum.take(model.variables, model.extra.n)
|> Enum.reduce(
MapSet.new(),
fn v, acc -> MapSet.put(acc, v.name) end
)
{
Strategy.mixed([:most_constrained, :dom_deg, :first_fail]),
# :dom_deg,
:indomain_max
}
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.extra.distances,
model.extra.weights
) &&
Logger.warning("#{@checkmark_symbol} #{ans_str}")) ||
Logger.error("#{@failure_symbol} #{ans_str}" <> ": wrong -((")
end)
end
end
def check_solution(solution, distances, weights) do
n = length(distances)
assignments = Enum.take(solution, n)
## In the solution, total cost follows assignments
total_cost = Enum.at(solution, n)
sum =
for i <- 0..(n - 2), j <- (i + 1)..(n - 1), reduce: 0 do
acc ->
assignment_i = Enum.at(assignments, i)
assignment_j = Enum.at(assignments, j)
d = distances |> Enum.at(assignment_i) |> Enum.at(assignment_j)
w = weights |> Enum.at(i) |> Enum.at(j)
acc + d * w
end
total_cost == sum
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))
weights =
lines
|> Enum.take(n)
|> parse_matrix()
distances =
lines
|> Enum.take(-n)
|> parse_matrix()
{n, distances, weights}
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