Packages
fixpoint
0.15.6
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/constraints/propagators/maximum.ex
defmodule CPSolver.Propagator.Maximum do
use CPSolver.Propagator
@moduledoc """
The propagator for Maximum constraint.
maximum(y, x) constrains y to be a maximum of variables in the list x.
"""
@spec new(Common.variable_or_view(), [Common.variable_or_view()]) :: Propagator.t()
def new(max_var, vars) do
new([max_var | vars])
end
@impl true
def arguments(args) do
Arrays.new(args, implementation: Aja.Vector)
end
@impl true
def variables(vars) do
Enum.map(vars, fn var -> set_propagate_on(var, :bound_change) end)
end
@impl true
def filter(vars, state, changes) do
if state do
reduce_state(state, vars, changes)
else
initial_state(vars)
end
|> finalize(vars)
end
defp initial_state(vars) do
array_length = Propagator.arg_size(vars) - 1
%{
active_var_indices: MapSet.new(1..array_length)
}
## Initialize reduction by the 'max' variable change
|> reduce_state(vars, %{0 => :bound_change})
end
defp finalize(state, vars) do
if exists_fixed_to_max(state, vars) do
:passive
else
{:state, state}
end
end
defp exists_fixed_to_max(%{active_var_indices: active_var_indices} = _state, vars) do
max_var = vars[0]
if fixed?(max_var) do
fixed_max = min(max_var)
Enum.any?(active_var_indices, fn idx ->
var = vars[idx]
fixed?(var) && min(var) == fixed_max
end)
end
end
defp no_support?(_max_var, active_var_indices, _vars) do
Enum.empty?(active_var_indices)
end
defp reduce_state(
%{
active_var_indices: active_var_indices,
} = state, vars,
_changes) do
max_var = vars[0]
min_max = min(max_var)
max_max = max(max_var)
{lb, ub, active_var_indices} =
## Try to reduce "array" variables
Enum.reduce(active_var_indices, {nil, nil, active_var_indices}, fn idx, {min_acc, max_acc, active_acc} = _acc ->
x_var = vars[idx]
removeAbove(x_var, max_max)
active_acc = if max(x_var) < min_max do
## The domain of the element is disjoint with domain of "max" variable.
## Hence we will ignore them
MapSet.delete(active_acc, idx)
else
active_acc
end
x_min = min(x_var)
x_max = max(x_var)
{
Kernel.max(min_acc || x_min, x_min),
Kernel.max(max_acc || x_max, x_max),
active_acc
}
end)
## If no "active" array variables (sucn that max(X) >= max(y)),
## then there is no support for y => failure
if no_support?(max_var, active_var_indices, vars) do
fail()
end
## Reduce 'max' var
removeAbove(max_var, ub)
removeBelow(max_var, lb)
## Special case: if there is a unique element X
## that:
## a) has a support for min(max_var)
## b) min(X) < min(max_var)
##
##, then we can reduce it below min(max_var)
##
try_reduce_x(max_var, vars, active_var_indices)
state
|> Map.put(:active_var_indices, active_var_indices)
end
defp try_reduce_x(max_var, vars, indices) do
min_max_value = min(max_var)
case Enum.reduce_while(indices, {false, nil}, fn idx, {found_support?, _supporting_idx} = acc ->
if contains?(vars[idx], min_max_value) do
if found_support? do
## More than one such element
{:halt, {false, nil}}
else
## First element
{:cont, {true, idx}}
end
else
{:cont, acc}
end
end) do
{false, nil} -> false
{true, supporting_idx} ->
:no_change != removeBelow(vars[supporting_idx], min_max_value)
end
end
defp fail() do
throw(:fail)
end
end