Packages
fixpoint
0.9.7
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
def select(variables, data, chb_mode)
when chb_mode in [:chb_min, :chb_max, :chb_size_min, :chb_size_max] do
select_impl(variables, data, chb_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
@doc """
Initialize CHB data
"""
def initialize(%{variables: variables} = space_data, q_score \\ @default_q_score) 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, q_score)
Shared.put_auxillary(shared, :chb, %{variable_chbs: chb_table})
)
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
%{variable_chbs: chb_table} = Shared.get_auxillary(shared, :chb)
Enum.each(variables, fn var -> update_variable_chb(var, chb_table, failure?, shared) end)
end
## Update chb for individual variable in 'shared'
defp update_variable_chb(%{id: variable_id} = variable, chb_table, failure?, shared) do
global_failure_count = Shared.get_failure_count(shared)
cond do
pruned?(variable) ->
chb = get_chb(chb_table, variable_id)
updated_chb =
%{chb | q_score: q_score(chb, failure?, shared)}
|> then(fn rec -> (failure? && %{rec | last_failure: global_failure_count}) || rec end)
:ets.insert(chb_table, {variable_id, updated_chb})
true ->
:ignore
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?,
shared
) do
global_failure_count = Shared.get_failure_count(shared)
alpha = step_size(global_failure_count)
reward =
((failure? && 1) || 0.9) / (global_failure_count - last_failure + 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