Packages
fixpoint
0.12.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.FirstFail do
use ExUnit.Case
alias CPSolver.IntVariable, as: Variable
alias CPSolver.DefaultDomain, as: Domain
alias CPSolver.Search
alias CPSolver.Search.Partition
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)
# first_fail chooses among unfixed variables
selected_variable = SearchStrategy.select_variable(variables, nil, :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, [{min_value_partition, _equal_constraint}, {no_min_partition, _not_equal_constraint}]} =
Partition.partition(selected_variable, :indomain_min)
min_value = Domain.min(min_value_partition)
assert Domain.to_list(no_min_partition) |> Enum.sort() ==
List.delete(Enum.to_list(v2_values), min_value) |> Enum.sort()
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)
assert catch_throw(Search.branch(variables, {:first_fail, :indomain_min})) ==
SearchStrategy.all_vars_fixed_exception()
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)
[b_left, b_right] =
branches = Search.branch(variables, {:first_fail, :indomain_min})
refute b_left == b_right
## Each branch has the same number of variables, as the original list of vars
assert Enum.all?(branches, fn {branch, _constraint} ->
Arrays.size(branch) == length(variables)
end)
## Left branch contains v2 variable fixed at 0
assert Enum.at(b_left |> elem(0), 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 Enum.at(b_right |> elem(0), 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)
[var1, var2] = MaxRegretSelector.select(variables, :ignore, :ignore)
## 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
var = Variable.new([1, 2, 3, 4, 5])
{:ok, [p1, p2]} = Partition.partition(var, :indomain_split)
p1_domain = elem(p1, 0)
assert Domain.to_list(p1_domain) == MapSet.new([1, 2, 3])
p2_domain = elem(p2, 0)
assert Domain.to_list(p2_domain) == MapSet.new([4, 5])
end
end
end