Packages
fixpoint
0.12.9
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/search/strategy/variable/shared/chb.ex
defmodule CPSolver.Search.VariableSelector.CHB do
@moduledoc """
Conflict-history based variable selector
(https://www.gecode.org/doc-latest/MPG.pdf, p.8.5.4)
"""
use CPSolver.Search.VariableSelector
alias CPSolver.Space
alias CPSolver.Shared
alias CPSolver.Variable.Interface
alias CPSolver.Utils
@default_q_score 0.05
@impl true
def select(variables, data, opts) do
select_impl(variables, data, opts[:mode])
|> Enum.map(fn {var, _chb} -> var end)
end
defp select_impl(variables, data, :chb_min) do
Utils.minimals(
variable_chbs(variables, Space.get_shared(data)),
fn {_var, %{q_score: q_score} = _chb} -> q_score end
)
end
defp select_impl(variables, data, :chb_max) do
Utils.maximals(
variable_chbs(variables, Space.get_shared(data)),
fn {_var, %{q_score: q_score} = _chb} -> q_score end
)
end
defp select_impl(variables, data, :chb_size_min) do
Utils.minimals(
variable_chbs(variables, Space.get_shared(data)),
fn {var, %{q_score: q_score} = _chb} ->
q_score / Interface.size(var)
end
)
end
defp select_impl(variables, data, :chb_size_max) do
Utils.maximals(
variable_chbs(variables, Space.get_shared(data)),
fn {var, %{q_score: q_score} = _chb} ->
q_score / Interface.size(var)
end
)
end
def default_q_score() do
@default_q_score
end
@doc """
Initialize CHB data
"""
@impl true
def initialize(%{variables: variables} = space_data, opts) do
shared = Space.get_shared(space_data)
Shared.get_auxillary(shared, :chb) ||
(
chb_table = Shared.create_shared_ets_table(shared)
init_variable_chbs(variables, chb_table, opts[:q_score] || @default_q_score)
Shared.put_auxillary(shared, :chb, %{variable_chbs: chb_table})
Shared.add_handler(shared, :on_space_finalized,
fn solver, %{variables: variables} = _space_data, reason ->
Shared.complete?(solver) ||
update_chbs(variables, reason == :failure, solver)
end)
)
end
defp init_variable_chbs(variables, chb_table, q_score) do
Enum.each(variables, fn var ->
:ets.insert(chb_table, {Interface.id(var), chb_record(q_score, 0)})
end)
end
defp chb_record(q_score, last_failure) do
%{q_score: q_score, last_failure: last_failure}
end
@doc """
Compute chbs of variables in one pass
"""
def variable_chbs(variables, shared) do
chb_data = Shared.get_auxillary(shared, :chb)
if chb_data do
%{variable_chbs: chb_table} = chb_data
chbs =
:ets.select(
chb_table,
for(var <- variables, do: {{Interface.id(var), :_}, [], [:"$_"]})
)
|> Map.new()
Enum.map(variables, fn var ->
var_id = Interface.id(var)
{var, Map.get(chbs, var_id, chb_record(@default_q_score, 0))}
end)
else
Enum.map(variables, fn var -> {var, chb_record(@default_q_score, 0)} end)
end
end
def update_chbs(variables, failure?, shared) do
case Shared.get_auxillary(shared, :chb) do
nil -> :ok
%{variable_chbs: chb_table} ->
Enum.reduce_while(variables, :ok,
fn var, _acc ->
Shared.complete?(shared) && {:halt, :ok} ||
(
update_variable_chb(var, chb_table, failure?, shared)
{:cont, :ok}
)
end)
end
end
## Update chb for individual variable in 'shared'
defp update_variable_chb(%{id: variable_id} = variable, chb_table, failure?, shared) do
case Shared.get_failure_count(shared) do
global_failure_count when is_integer(global_failure_count) ->
cond do
pruned?(variable) ->
chb = get_chb(chb_table, variable_id)
updated_chb =
%{chb | q_score: q_score(chb, failure?, global_failure_count)}
|> then(fn rec -> (failure? && %{rec | last_failure: max(chb.last_failure, global_failure_count)}) || rec end)
:ets.insert(chb_table, {variable_id, updated_chb})
true ->
:ignore
end
_ -> :ok
end
end
defp pruned?(%{initial_size: initial_size} = variable) do
current_size =
try do
Interface.size(variable)
catch
:fail ->
0
end
initial_size > current_size
end
defp q_score(
%{q_score: current_qs, last_failure: last_failure} = _current_chb_record,
failure?,
global_failure_count
) do
alpha = step_size(global_failure_count)
reward =
((failure? && 1) || 0.9) / (max(global_failure_count - last_failure, 0) + 1)
(1 - alpha) * current_qs + alpha * reward
end
def step_size(failure_count) do
max(0.06, 0.4 - failure_count * 1.0e-6)
end
defp get_chb(table, variable_id)
when is_reference(table) and is_reference(variable_id) do
table
|> :ets.lookup(variable_id)
|> then(fn rec ->
(!Enum.empty?(rec) && elem(hd(rec), 1)) ||
chb_record(@default_q_score, 0)
end)
end
end