Packages
fixpoint
0.2.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/solver/core/solver.ex
defmodule CPSolver do
@moduledoc """
Solver API.
"""
alias CPSolver.Space
use GenServer
require Logger
@doc """
"""
@spec solve(Model.t(), Keyword.t()) :: any()
def solve(model, opts \\ []) do
{:ok, _solver} = GenServer.start_link(CPSolver, [model, opts])
end
def statistics(solver) when is_pid(solver) do
GenServer.call(solver, :get_stats)
end
def solutions(solver) when is_pid(solver) do
GenServer.call(solver, :get_solutions)
end
## GenServer callbacks
@impl true
def init([%{constraints: constraints, variables: variables} = _model, solver_opts]) do
propagators =
Enum.reduce(constraints, [], fn constraint, acc ->
acc ++ constraint_to_propagators(constraint)
end)
stop_on = Keyword.get(solver_opts, :stop_on)
{:ok,
%{
space: nil,
variables: variables,
propagators: propagators,
solution_count: 0,
failure_count: 0,
node_count: 1,
solutions: [],
active_nodes: MapSet.new(),
stop_on: stop_on,
solver_opts: solver_opts
}, {:continue, :solve}}
end
defp constraint_to_propagators(constraint) do
[constraint_mod | args] = Tuple.to_list(constraint)
constraint_mod.propagators(args)
end
@impl true
def handle_continue(
:solve,
%{variables: variables, propagators: propagators, solver_opts: solver_opts} = state
) do
{:ok, top_space} =
Space.create(variables, propagators, Keyword.put(solver_opts, :solver, self()))
{:noreply, Map.put(state, :space, top_space)}
end
@impl true
def handle_info(event, state) do
{:noreply, handle_event(event, state)}
end
defp handle_event(
{:solution, new_solution},
%{solution_count: count, solutions: solutions, stop_on: stop_on} = state
) do
if check_for_stop(stop_on, new_solution, state) do
stop_spaces(state)
else
%{state | solution_count: count + 1, solutions: [new_solution | solutions]}
end
## TODO: check for stopping condition here.
## Q: spaces are async and handle solutions on their own,
## so even if stopping condition is handled here, how do (or should)
## we prevent spaces from emitting new solutions?
end
defp handle_event(:failure, %{failure_count: count} = state) do
Logger.debug("Solver: space failure")
%{state | failure_count: count + 1}
end
defp handle_event({:nodes, new_nodes}, %{node_count: count, active_nodes: nodes} = state) do
new_nodes_set = MapSet.new(new_nodes)
n = MapSet.size(new_nodes_set)
Logger.debug("Solver: #{n} new node(s)")
%{state | node_count: count + n, active_nodes: MapSet.union(nodes, new_nodes_set)}
end
defp handle_event({:shutdown_space, node}, %{active_nodes: nodes} = state) do
%{state | active_nodes: MapSet.delete(nodes, node)}
end
defp handle_event(unexpected, state) do
Logger.error("Solver: unexpected message #{inspect(unexpected)}")
state
end
@impl true
def handle_call(:get_stats, _from, state) do
{:reply, get_stats(state), state}
end
def handle_call(:get_solutions, _from, state) do
{:reply, get_solutions(state), state}
end
defp get_stats(state) do
Map.take(state, [:solution_count, :failure_count, :node_count])
end
defp get_solutions(%{solutions: solutions} = _state) do
## Here we piggy-back on the fact that the variables are ordered by their refs
## in spaces, and the order there matches the order within solver state.
## This may likely change, we will probably use var names instead of refs.
solutions
|> Enum.map(fn solution ->
solution
|> Enum.sort_by(fn {ref, _value} -> ref end)
|> Enum.map(fn {_ref, value} -> value end)
end)
end
defp check_for_stop(nil, _solution, _data) do
false
end
defp check_for_stop({:max_solutions, max}, _solution, data) do
max == data.solution_count
end
defp check_for_stop(condition, solution, data) when is_function(condition, 2) do
condition.(solution, data)
end
defp stop_spaces(%{active_nodes: spaces} = data) do
Enum.each(spaces, fn s -> Process.alive?(s) && Process.exit(s, :kill) end)
data
end
end