Packages
fixpoint
0.6.3
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/solver/space/space.ex
defmodule CPSolver.Space do
@moduledoc """
Computation space.
The concept is taken from Chapter 12, "Concepts, Techniques, and Models
of Computer Programming" by Peter Van Roy and Seif Haridi.
"""
alias CPSolver.Utils
alias CPSolver.ConstraintStore
alias CPSolver.Solution, as: Solution
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Propagator.ConstraintGraph
alias CPSolver.Utils
alias CPSolver.Space.Propagation
alias CPSolver.Objective
alias CPSolver.Shared
require Logger
@behaviour GenServer
def default_space_opts() do
[
store_impl: CPSolver.ConstraintStore.default_store(),
solution_handler: Solution.default_handler(),
search: CPSolver.Search.Strategy.default_strategy(),
postpone: false
]
end
def create(variables, propagators, space_opts \\ default_space_opts()) do
propagators = maybe_add_objective_propagator(propagators, space_opts[:objective])
{:ok, _space} =
create(%{
variables: variables,
propagators: propagators,
constraint_graph: ConstraintGraph.create(propagators),
opts: space_opts
})
end
defp maybe_add_objective_propagator(propagators, nil) do
propagators
end
defp maybe_add_objective_propagator(propagators, objective) do
[objective.propagator | propagators]
end
def create(data) do
if CPSolver.complete?(data.opts[:solver_data]) do
{:error, :complete}
else
GenServer.start(__MODULE__, data)
end
end
def start_propagation(space_pid) when is_pid(space_pid) do
:done = GenServer.call(space_pid, :propagate, :infinity)
end
@impl true
def init(%{variables: variables, opts: space_opts, constraint_graph: graph} = data) do
{:ok, space_variables, store} =
ConstraintStore.create_store(variables,
store_impl: space_opts[:store_impl],
space: self()
)
space_data =
data
|> maybe_bind_objective_variable(store)
|> Map.put(:id, make_ref())
|> Map.put(:variables, space_variables)
|> Map.put(:store, store)
|> Map.put(:constraint_graph, ConstraintGraph.remove_fixed(graph, space_variables))
Shared.add_active_spaces(data.opts[:solver_data], [self()])
{:ok, space_data, {:continue, :propagate}}
end
defp maybe_bind_objective_variable(data, store) do
case data.opts[:objective] do
nil ->
data
objective ->
put_in(data, [:opts, :objective], Objective.bind_to_store(objective, store))
end
end
@impl true
def handle_continue(:propagate, data) do
(data.opts[:postpone] && {:noreply, data}) ||
data
|> propagate()
|> tap(fn _ ->
caller = Map.get(data, :caller)
caller && GenServer.reply(caller, :done)
end)
end
@impl true
def handle_call(:propagate, caller, data) do
{:noreply,
data
|> Map.put(:caller, caller)
|> Map.put(:opts, Keyword.put(data.opts, :postpone, false)), {:continue, :propagate}}
end
defp propagate(
%{
propagators: propagators,
variables: variables,
constraint_graph: constraint_graph,
store: store
} =
data
) do
case Propagation.run(propagators, constraint_graph, store) do
:fail ->
handle_failure(data)
:solved ->
handle_solved(data)
{:stable, reduced_constraint_graph, reduced_propagators} ->
%{
data
| constraint_graph: reduced_constraint_graph,
propagators: reduced_propagators,
variables: variables
}
|> handle_stable()
end
end
defp handle_failure(data) do
shutdown(data, :failure)
end
defp handle_solved(data) do
data
|> solution()
|> then(fn
:fail ->
shutdown(data, :fail)
solution ->
maybe_tighten_objective_bound(data.opts[:objective])
Solution.run_handler(solution, data.opts[:solution_handler])
shutdown(data, :solved)
end)
end
defp solution(%{variables: variables, store: store} = _data) do
Enum.reduce_while(variables, Map.new(), fn var, acc ->
case ConstraintStore.get(store, var, :min) do
:fail -> {:halt, :fail}
val -> {:cont, Map.put(acc, var.name, val)}
end
end)
end
defp maybe_tighten_objective_bound(nil) do
:ok
end
defp maybe_tighten_objective_bound(objective) do
Objective.tighten(objective)
end
defp handle_stable(%{variables: variables} = data) do
{localized_vars, _all_fixed?} = Utils.localize_variables(variables)
distribute(%{data | variables: localized_vars})
end
def distribute(
%{
opts: opts,
variables: localized_variables
} = data
) do
{:ok, {var_to_branch_on, domain_partitions}} = branching(localized_variables, opts[:search])
Enum.take_while(domain_partitions, fn partition ->
variable_copies =
Enum.map(localized_variables, fn %{id: clone_id} = clone ->
if clone_id == var_to_branch_on.id do
Map.put(clone, :domain, Domain.new(partition))
else
clone
end
end)
case create(
data
|> Map.put(:variables, variable_copies)
|> Map.put(:opts, Keyword.put(data.opts, :postpone, true))
) do
{:ok, space_pid} -> spawn(fn -> start_propagation(space_pid) end)
{:error, :complete} -> false
end
end)
shutdown(data, :distribute)
end
defp branching(variables, search_strategy) do
case search_strategy.select_variable(variables) do
{:ok, var_to_branch_on} ->
var_domain = var_to_branch_on.domain
case search_strategy.partition(var_domain) do
:fail -> :fail
{:ok, partitions} -> {:ok, {var_to_branch_on, partitions}}
end
error ->
error
end
end
defp shutdown(data, reason) do
Shared.remove_space(data.opts[:solver_data], self(), reason)
{:stop, :normal, data}
end
end