fixpoint

0.16.4

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

HexDocs

Current section

Files

Jump to

Readme 187 Versions 5 Dependencies Dependants Files Activity

fixpoint lib solver constraints constraint_factory.ex

Raw

lib/solver/constraints/constraint_factory.ex

defmodule CPSolver.Constraint.Factory do
  alias CPSolver.Constraint.{
    Sum,
    ElementVar,
    Element2D,
    Maximum,
    Minimum,
    Modulo,
    Absolute,
    Less,
    LessOrEqual,
    Equal,
    Reified,
    AllDifferent
  }

  alias CPSolver.Propagator.Modulo, as: ModuloPropagator
  alias CPSolver.IntVariable, as: Variable
  alias CPSolver.BooleanVariable
  alias CPSolver.Variable.Interface
  import CPSolver.Variable.View.Factory
  import CPSolver.Utils

  def element(array, x, y) do
    ElementVar.new(array, x, y)
  end

  def element(array, x) do
    y_domain =
      Enum.reduce(array, MapSet.new(), fn el, acc ->
        domain_values(el) |> MapSet.union(acc)
      end)
      |> MapSet.to_list()

    y = Variable.new(y_domain)
    result(y, element(array, x, y))
  end

  def element2d(array2d, x, y) do
    domain = array2d |> List.flatten()
    z = Variable.new(domain)
    result(z, element2d(array2d, x, y, z))
  end

  def element2d(array2d, x, y, z) do
    Element2D.new([array2d, x, y, z])
  end

  def element2d_var(array2d, x, y, z) do
    num_rows = length(array2d)
    num_cols = length(hd(array2d))
    Interface.removeBelow(x, 0)
    Interface.removeAbove(x, num_rows - 1)
    Interface.removeBelow(y, 0)
    Interface.removeAbove(y, num_cols - 1)

    {flat_idx_var, sum_constraint} = add(mul(x, num_cols), y)
    Interface.removeBelow(flat_idx_var, 0)
    Interface.removeAbove(flat_idx_var, num_rows * num_cols - 1)
    element_constraint = element(List.flatten(array2d), flat_idx_var, z)
    [sum_constraint, element_constraint]
  end

  def element2d_var(array2d, x, y) do
    domain =
      Enum.reduce(array2d |> List.flatten(), MapSet.new(), fn el, acc ->
        domain_values(el)
        |> MapSet.union(acc)
      end)
      |> MapSet.to_list()

    z = Variable.new(domain)
    result(z, element2d_var(array2d, x, y, z))
  end

  def equal(x, y) do
    Equal.new(x, y)
  end

  def less(x, y) do
    Less.new(x, y)
  end

  def leq(x, y) do
    LessOrEqual.new(x, y)
  end

  def maximum(vars, max_var) do
    Maximum.new(max_var, vars)
  end

  def maximum(vars) do
    domain = Enum.reduce(vars, MapSet.new(), fn var, acc ->
      MapSet.union(acc, domain_values(var))
    end)

    max_var = Variable.new(domain)
    result(max_var, Maximum.new(max_var, vars))
  end

  def minimum(vars, min_var) do
    Minimum.new(min_var, vars)
  end

  def minimum(vars) do
    domain = Enum.reduce(vars, MapSet.new(), fn var, acc ->
      MapSet.union(acc, domain_values(var))
    end)

    min_var = Variable.new(domain)
    result(min_var, Minimum.new(min_var, vars))
  end


  def sum(vars, sum_var) do
    Sum.new(sum_var, vars)
  end

  def sum(vars) do
    {domain_min, domain_max} =
      Enum.reduce(vars, {0, 0}, fn var, {min_acc, max_acc} ->
        domain = domain_values(var)
        {min_acc + Enum.min(domain), max_acc + Enum.max(domain)}
      end)

    domain = domain_min..domain_max

    sum_var = Variable.new(domain)
    result(sum_var, Sum.new(sum_var, vars))
  end

  def count(array, y, c) do
    {b_vars, reif_constraints} =
      for a <- array, reduce: {[], []} do
        {vars_acc, constraints_acc} ->
          b = BooleanVariable.new()
          equal_p = Reified.new(Equal.new(a, y), b)
          {[b | vars_acc], [equal_p | constraints_acc]}
      end

    Interface.removeBelow(c, 0)
    Interface.removeAbove(c, length(array))
    [Sum.new(c, b_vars) | reif_constraints]
  end

  def inverse(f, inv_f) do
    length(f) == length(inv_f) ||
      throw("Inverse constraint has to have sizes of arguments match")

    index_set = MapSet.new(0..(length(f) - 1))

    for i <- index_set do
      f_i = Enum.at(f, i)
      inv_f_i = Enum.at(inv_f, i)

      (MapSet.subset?(domain_values(f_i), index_set) &&
         MapSet.subset?(domain_values(inv_f_i), index_set)) ||
        throw("Inverse constraint has to have all variable domains within index_set")

      [
        element(f, inv_f_i, i),
        element(inv_f, f_i, i)
      ]
    end
    |> List.flatten()
    |> Enum.concat([AllDifferent.DC.new(f), AllDifferent.DC.new(inv_f)])
  end

  def add(var1, var2) do
    sum([var1, var2])
  end

  def subtract(var1, var2) do
    add(var1, linear(var2, -1, 0))
  end

  def mod(x, y) do
    {lb, ub} = ModuloPropagator.mod_bounds(x, y)

    domain =
      lb..ub

    mod_var = Variable.new(domain)
    result(mod_var, Modulo.new(mod_var, x, y))
  end

  def mod(mod_var, x, y) do
    Modulo.new(mod_var, x, y)
  end

  def absolute(x) do
    abs_min = abs(Interface.min(x))
    abs_max = abs(Interface.max(x))
    domain = 0..max(abs_min, abs_max)

    abs_var = Variable.new(domain)
    result(abs_var, Absolute.new(x, abs_var))
  end

  def absolute(x, abs_var) do
    Absolute.new(x, abs_var)
  end

  def alldifferent(vars) do
    AllDifferent.new(vars)
  end


  defp compose(constraint1, constraint2, relation) do
    b1 = BooleanVariable.new()
    b2 = BooleanVariable.new()
    reif_c1 = Reified.new([constraint1, b1])
    reif_c2 = Reified.new([constraint2, b2])
    %{constraints: [reif_c1, reif_c2, relation.new([b1, b2])], derived_variables: [b1, b2]}
  end

  ## Implication, equivalence, inverse implication.
  ## These function produce the list of constraints:
  ## - 2 reified constraints for constraint1 and constraint2
  ## - relational constraint (LessOrEqual for implications, Equal for equivalence)
  ## over control variables induced by reified constraints.
  ##
  def impl(constraint1, constraint2) do
    compose(constraint1, constraint2, LessOrEqual)
  end

  def equiv(constraint1, constraint2) do
    compose(constraint1, constraint2, Equal)
  end

  def inverse_impl(constraint1, constraint2) do
    impl(constraint2, constraint1)
  end

  defp result(derived_variable, constraint) do
    {derived_variable, constraint}
  end
end

Operator	Description	Example
name:	Match package name. Supports * wildcards and repo/package form	name:phx* or name:hexpm/phoenix
description:	Full-text search of package descriptions	description:auth
depends:	Packages depending on a given package. Supports repo:package form	depends:ecto or depends:hexpm:ecto
build_tool:	Filter by build tool	build_tool:mix
updated_after:	Packages updated after an ISO8601 datetime	updated_after:2025-01-01T00:00:00Z
extra:	Match custom metadata (key,value). Nested keys are separated by commas	extra:license,MIT