Packages
fixpoint
0.22.2
0.22.2
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
test/search/search_strategy_test.exs
defmodule CPSolverTest.Search.Brancher do
use ExUnit.Case
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Variable.Interface
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search
alias CPSolver.Search.Partition
alias CPSolver.Utils.Vector
alias CPSolver.Variable.UnfixedTracker, as: Tracker
describe "First-fail search strategy" do
alias CPSolver.Search.VariableSelector, as: SearchStrategy
test ":first_fail and :indomain_min" do
v0_values = 0..0
v1_values = 1..10
# This domain (will be assigned to `v2` variable) is the smallest among unfixed
v2_values = 0..5
v3_values = 1..1
v4_values = -5..5
values = [v0_values, v1_values, v2_values, v3_values, v4_values]
variables = Enum.map(values, fn d -> Variable.new(d) end) |> Vector.new()
state = %{variables: variables, unfixed_variables_tracker: Tracker.new(variables)}
# first_fail chooses among unfixed variables
selected_variable = SearchStrategy.select_variable(state, :first_fail)
assert selected_variable.id in Enum.map([1, 2, 4], fn var_pos ->
Enum.at(variables, var_pos) |> Map.get(:id)
end)
# indomain_min splits domain of selected variable into min and the rest of the domain
{:ok, [fixed_value_partition, _removed_value_partition]} =
Partition.partition(selected_variable, :indomain_min)
## Apply the 'partition' function
fixed_value_fun = Map.get(fixed_value_partition, selected_variable.id)
refute Interface.fixed?(selected_variable)
fixed_value_fun.(selected_variable)
assert Interface.fixed?(selected_variable)
end
test "first_fail fails if no unfixed variables" do
v0_values = 0..0
v1_values = 1..1
v2_values = -2..-2
v3_values = 1..1
v4_values = 5..5
values = [v0_values, v1_values, v2_values, v3_values, v4_values]
variables = Enum.map(values, fn d -> Variable.new(d) end)
state = %{variables: variables, unfixed_variables_tracker: Tracker.new(variables)}
assert catch_throw(Search.branch({:first_fail, :indomain_min}, state)) ==
:all_vars_fixed
end
test "branch creation" do
v0_values = 0..0
v1_values = 1..10
# This domain is the smallest among unfixed
v2_values = 0..5
v3_values = 1..1
v4_values = -5..5
values = [v0_values, v1_values, v2_values, v3_values, v4_values]
variables = Enum.map(values, fn d -> Variable.new(d) end) |> Vector.new()
state =%{variables: variables, unfixed_variables_tracker: Tracker.new(variables)}
[b_left, b_right] =
branches =
Search.branch({:first_fail, :indomain_min}, state)
|> Enum.map(fn partition_fun -> partition_fun.(state) end)
refute b_left == b_right
## Each branch has the same number of variables, as the original list of vars
assert Enum.all?(branches, fn %{variable_copies: branch_variables} ->
Vector.size(branch_variables) == Vector.size(variables)
end)
## Left branch contains v2 variable fixed at 0
assert Vector.at(b_left |> Map.get(:variable_copies), 2)
|> Map.get(:domain)
|> then(fn domain -> Domain.size(domain) == 1 && Domain.min(domain) == 0 end)
## Right branch contains v2 variable with 0 removed
refute Vector.at(b_right |> Map.get(:variable_copies), 2) |> Map.get(:domain) |> Domain.contains?(0)
end
end
describe "Misc strategies" do
alias CPSolver.Search.VariableSelector.MaxRegret, as: MaxRegretSelector
test "max_regret selector" do
domains = [1..3, [2, 10, 11], [3, 12, 15], [6, 15]]
variables =
Enum.map(Enum.with_index(domains, 1), fn {d, idx} -> Variable.new(d, name: idx) end)
|> Vector.new()
space_data = %{unfixed_variables_tracker: Tracker.new(variables), variables: variables}
[var1, var2] = MaxRegretSelector.select(space_data, [])
## Chooses variables with largest difference between 2 smallest values
## diff(1) = 1, diff(2) = 8, diff(3) = diff(4) = 9
assert var1.name in [3, 4] && var2.name in [3, 4]
end
test "indomain_split" do
domain = [1, 2, 3, 4, 5]
{part1, part2} = Enum.split(domain, div(length(domain), 2))
variable = Variable.new(domain)
{:ok, [p1, p2]} = Partition.partition(variable, :indomain_split)
## Apply the 'left-side partition' function
ls_partition_fun = Map.get(p1, variable.id)
variable_copy = Variable.new(domain)
ls_partition_fun.(variable_copy)
assert CPSolver.Utils.domain_values(variable_copy) == MapSet.new(part1)
## Apply the 'right-side partition' function
rs_partition_fun = Map.get(p2, variable.id)
variable_copy = Variable.new(domain)
rs_partition_fun.(variable_copy)
assert CPSolver.Utils.domain_values(variable_copy) == MapSet.new(part2)
end
end
end