Propagators

NuCS currently provides the following highly-optimized propagators.

nucs.propagators.abs_eq_propagator.compute_domains_abs_eq(...) → int

Implements \(abs(y)=x\).

Parameters:

• domains (NDArray) – the domains of the variables, y is the first domain, x the second

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.add_c_eq_propagator.compute_domains_add_c_eq(...) → int

Implements \(x + c = y\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y the second

• parameters (NDArray) – the constant c, parameters[0]

Returns:

the status of the propagation (consistency or inconsistency) as an int

Return type:

int

nucs.propagators.linear_eq_c_propagator.compute_domains_linear_eq_c(...) → int

Implements \(\sum_i a_i * x_i = a_{n}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is an alias for parameters

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.linear_geq_c_propagator.compute_domains_linear_geq_c(...) → int

Implements \(\sum_i a_i * x_i >= a_{n}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is an alias for parameters

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.linear_leq_c_propagator.compute_domains_linear_leq_c(...) → int

Implements \(\sum_i a_i * x_i <= a_{n}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is an alias for parameters

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.linear_neq_c_propagator.compute_domains_linear_neq_c(...) → int

Implements \(\sum_i a_i * x_i \neq a_{n}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is an alias for parameters

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.alldifferent_propagator.compute_domains_alldifferent(...) → int

Enforces that \(x_i <> x_j when i<>j\).

Adapted from “A fast and simple algorithm for bounds consistency of the alldifferent constraint”. :param domains: the domains of the variables, x is an alias for domains :type domains: NDArray :param parameters: either empty or offsets :type parameters: NDArray

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.and_eq_propagator.compute_domains_and_eq(...) → int

Implements \(\& b_i = b_{n-1}\) where for each i, b_i is a boolean variable.

Parameters:

• domains (NDArray) – the domains of the variables, b is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.count_eq_c_propagator.compute_domains_count_eq_c(...) → int

Implements \(\sum_i (x_i == a) = c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is the first parameter, c is the second parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.count_eq_propagator.compute_domains_count_eq(...) → int

Implements \(\sum_i (x_i == a) = x_{n-1}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.count_geq_c_propagator.compute_domains_count_geq_c(...) → int

Implements \(\sum_i (x_i == a) >= c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is the first parameter, c is the second parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.count_leq_c_propagator.compute_domains_count_leq_c(...) → int

Implements \(S\sum_i (x_i == a) <= c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, a is the first parameter, c is the second parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.cumulative_propagator.compute_domains_cumulative(...) → int

Implements the cumulative constraint: tasks with start times domains run for constant durations and consume constant amounts of a resource of fixed capacity; at no instant may the total consumption of the tasks in progress exceed the capacity.

Filtering combines timetabling and energetic reasoning: timetabling raises starts so that no task overlaps an instant already saturated by the other tasks’ compulsory parts (and lowers latest starts by mirroring time); energetic reasoning then, over a quadratic set of intervals, compares each task’s minimum mandatory energy against the capacity to detect overloads and push the bounds further. Neither rule is idempotent, so the whole block is iterated until a full sweep changes no bound, leaving the propagator at its own fixpoint. Both rules are incomplete, so the propagator may stay consistent on an infeasible instance – that is sound.

The parameters pack, in order, the n durations, then the n demands (heights), then the capacity: parameters = [p_0, ..., p_{n-1}, h_0, ..., h_{n-1}, capacity].

Parameters:

• domains (NDArray) – the domains of the start-time variables, one per task

• parameters (NDArray) – the durations, the demands and the capacity, as described above

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.diffn_propagator.compute_domains_diffn(...) → int

Implements the 2D diffn (non-overlapping rectangles) constraint. Rectangle i has its bottom-left corner at (x_i, y_i) and constant size (dx_i, dy_i); no two rectangles overlap, i.e. for all i != j at least one of x_i + dx_i <= x_j, x_j + dx_j <= x_i, y_i + dy_i <= y_j, y_j + dy_j <= y_i holds.

The first n variables are the x coordinates, the next n are the y coordinates. Filtering is pairwise: a pair that can no longer be separated along x (resp. y) must be separated along y (resp. x); when only one separation direction remains feasible it is enforced by tightening the coordinate bounds.

Parameters:

• domains (NDArray) – the domains of the variables, the n x coordinates then the n y coordinates

• parameters (NDArray) – the n widths (dx) then the n heights (dy)

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.disjunctive_propagator.compute_domains_disjunctive(...) → int

Implements the disjunctive (unary resource) constraint: tasks with start times domains and constant durations parameters must not overlap in time, i.e. for all i != j either s_i + p_i <= s_j or s_j + p_j <= s_i.

Filtering combines overload checking, edge finding, not-first/not-last and detectable precedences: each rule raises earliest start times, and lowers latest start times by running the same reasoning on the time-reversed problem. The rules are not individually idempotent, so the whole block is iterated until a full sweep changes no bound, leaving the propagator at its own fixpoint.

Parameters:

• domains (NDArray) – the domains of the start-time variables, one per task

• parameters (NDArray) – the durations, one constant per task in the same order as the variables

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.element_eq_propagator.compute_domains_element_eq(...) → int

Enforces \(l_i = v\).

Parameters:

• domains (NDArray) – the domains of the variables, i is the first domain, v is the last domain

• parameters (NDArray) – the parameters of the propagator, l is an alias for parameters

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.element_l_eq_alldifferent_propagator.compute_domains_element_l_eq_alldifferent(...) → int

Enforces \(l_i = v\) when alldifferent(l).

Parameters:

• domains (NDArray) – the domains of the variables, l is the list of the first n-2 domains, i is the (n-1)th domain, v is the last domain

• parameters (NDArray) – the parameters of the propagator, it is unused

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.element_l_eq_c_alldifferent_propagator.compute_domains_element_l_eq_c_alldifferent(...) → int

Enforces \(l_i = c\) when the elements of l are all different.

Parameters:

• domains (NDArray) – the domains of the variables, l is the list of the first n-1 domains, i is the last domain

• parameters (NDArray) – the parameters of the propagator, c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.element_l_eq_c_propagator.compute_domains_element_l_eq_c(...) → int

Enforces \(l_i = c\).

Parameters:

• domains (NDArray) – the domains of the variables, l is the list of the first n-1 domains, i is the last domain

• parameters (NDArray) – the parameters of the propagator, c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.element_l_eq_propagator.compute_domains_element_l_eq(...) → int

Enforces \(l_i = v\).

Parameters:

• domains (NDArray) – the domains of the variables, l is the list of the first n-2 domains, i is the (n-1)th domain, v is the last domain

• parameters (NDArray) – the parameters of the propagator, it is unused

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.eq_propagator.compute_domains_eq(...) → int

Implements \(x = y\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y the second

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.eq_c_reif_propagator.compute_domains_eq_c_reif(...) → int

Implements \(b <=> x = c\).

Parameters:

• domains (NDArray) – the domains of the variables, b is the first domain, x is the second domain

• parameters (NDArray) – c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.eq_reif_propagator.compute_domains_eq_reif(...) → int

Implements \(b <=> x = y\).

Parameters:

• domains (NDArray) – the domains of the variables, b is the first domain, x is the second, y is the third

• parameters (NDArray) – unused

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.gcc_propagator.compute_domains_gcc(...) → int

This propagator (Global Cardinality Constraint) enforces that \(l_j \le |\{ i : x_i = v_j \}| \le c_j\) for all j. It is adapted from “An efficient bounds consistency algorithm for the global cardinality constraint”.

Parameters:

• domains (NDArray) – the domains of the variables

• parameters (NDArray) – there are 1 + 2 * m parameters: the first domain value (v_0), then the m lower bounds, then the m upper bounds (capacities)

Returns:

a propagation status (PROP_INCONSISTENCY or PROP_CONSISTENCY)

Return type:

int

nucs.propagators.increasing_propagator.compute_domains_increasing(...) → int

Implements \(x_i <= x_{i+1}\) for all i.

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.inverse_propagator.compute_domains_inverse(...) → int

Channels two inverse arrays next and prev of equal length: prev[j] = i iff next[i] = j.

Parameters:

• domains (NDArray) – the domains of the variables, the next variables then the prev variables

• parameters (NDArray) – the parameters of the propagator, unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.leq_c_propagator.compute_domains_leq_c(...) → int

Implements \(x <= y + c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y is the second domain

• parameters (NDArray) – the parameters of the propagator, c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.leq_c_reif_propagator.compute_domains_leq_c_reif(...) → int

Implements \(b <=> x \leq y + a_0\).

Parameters:

• domains (NDArray) – the domains of the variables, b is the first domain, x is the second, y is the third

• parameters (NDArray) – the parameters of the propagator, a_0 is the constant added to y

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.lexleq_propagator.compute_domains_lexleq(...) → int

Implements lexicographic leq: \(x <_leq y\). See https://www.diva-portal.org/smash/record.jsf?pid=diva2:1041533.

Parameters:

• domains (NDArray) – the domains of the variables, x is the list of the first n domains, y is the list of the last n domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.max_eq_propagator.compute_domains_max_eq(...) → int

Implements \(\max_i x_i = x_{n-1}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.max_leq_propagator.compute_domains_max_leq(...) → int

Implements \(\max_i x_i <= x_{n-1}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.member_propagator.compute_domains_member(...) → int

Implements \(x \in \{a_0, ..., a_{n-1}\}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first (and only) domain

• parameters (NDArray) – the allowed values, in strictly ascending order

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.min_eq_propagator.compute_domains_min_eq(...) → int

Implements \(\min_i x_i = x_{n-1}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.min_geq_propagator.compute_domains_min_geq(...) → int

Implements \(\min_i x_i >= x_{n-1}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.mod_c_eq_propagator.compute_domains_mod_c_eq(...) → int

Implements \(x \bmod m = z\) for a constant modulus m, with truncated division (the remainder takes the sign of the dividend x), i.e. the FlatZinc/MiniZinc int_mod semantics with a fixed divisor.

The remainder is independent of the sign of m, so the modulus magnitude is used throughout and the negative part of x is mirrored onto the non-negative remainder arithmetic. Filtering is bound-consistent.

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, z the second

• parameters (NDArray) – the parameters, m is parameters[0]

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.mod_eq_propagator.compute_domains_mod_eq(...) → int

Implements \(x \bmod y = z\) with truncated division (the remainder takes the sign of the dividend x), i.e. the FlatZinc/MiniZinc int_mod semantics.

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y the second, z the third

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.mul_c_eq_propagator.compute_domains_mul_c_eq(...) → int

Implements \(x * c = y\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y the second

• parameters (NDArray) – the constant c, parameters[0]

Returns:

the status of the propagation (consistency or inconsistency) as an int

Return type:

int

nucs.propagators.mul_eq_propagator.compute_domains_mul_eq(...) → int

Implements \(x * y = z\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y the second, z the third

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.neq_propagator.compute_domains_neq(...) → int

Implements \(x \neq y\).

Parameters:

• domains (NDArray) – the domains of the variables, x is the first domain, y the second

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.neq_reif_propagator.compute_domains_neq_reif(...) → int

Implements \(b <=> x \neq y\).

Parameters:

• domains (NDArray) – the domains of the variables, b is the first domain, x is the second, y is the third

• parameters (NDArray) – unused

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.no_sub_cycle_propagator.compute_domains_no_sub_cycle(...) → int

Enforces that a permutation does not contain any sub-cycle.

Parameters:

• domains (NDArray) – the domains of the variables

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.nvalue_propagator.compute_domains_nvalue(...) → int

Implements \(y = |\{x_0, ..., x_{n-1}\}|\), the number of distinct values taken by the x_i.

Full domain consistency is NP-hard, so this bounds the count variable y between the maximum number of pairwise-disjoint domains (a guaranteed-distinct lower bound) and min(n, |union of the domains|), and handles the all-equal case y = 1 exactly.

Parameters:

• domains (NDArray) – the domains of the variables, x is the first n-1 domains, y is the last domain

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.relation_propagator.compute_domains_relation(...) → int

Implements a relation over n variables defined by its allowed tuples.

Parameters:

• domains (NDArray) – the domains of the variables

• parameters (NDArray) – the parameters of the propagator, the allowed tuples correspond to: (parameters_0, …, parameters_n-1), (parameters_n, …, parameters_2n-1), …

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.scc_propagator.compute_domains_scc(...) → int

Enforces that the digraph whose arcs are i -> j for j in [domains[i, MIN], domains[i, MAX]] is strongly connected.

A digraph is strongly connected iff, from any single root (node 0), every node is reachable (forward DFS) and the root is reachable from every node (backward DFS). Both searches are iterative with an explicit stack: the former recursive dfs_row / dfs_col helpers could not use cache=True because of a Numba issue with cached recursion.

The out-neighbors of every node form a contiguous interval, so the forward traversal never materializes the adjacency matrix and skips already-visited ranges via a union-find.

Parameters:

• domains (NDArray) – the domains of the variables

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.strictly_increasing_propagator.compute_domains_strictly_increasing(...) → int

Implements \(x_i < x_{i+1}\) for all i.

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.subcircuit_propagator.compute_domains_subcircuit(...) → int

Enforces that the 0-based successor array forms a sub-circuit: the nodes i with x_i != i form a single circuit while the remaining nodes are self-loops (x_i = i, excluded). The empty sub-circuit (all self-loops) is allowed. This is a self-loop-aware variant of the no-sub-cycle constraint and is meant to run alongside an alldifferent on the same variables.

Parameters:

• domains (NDArray) – the domains of the variables (0-based successors)

• parameters (NDArray) – unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.sum_eq_c_propagator.compute_domains_sum_eq_c(...) → int

Implements \(\sum_i x_i = c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.sum_eq_propagator.compute_domains_sum_eq(...) → int

Implements \(\sum_i x_i = x_{n-1}\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, unused here

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.sum_geq_c_propagator.compute_domains_sum_geq_c(...) → int

Implements \(\sum_i x_i >= c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.sum_leq_c_propagator.compute_domains_sum_leq_c(...) → int

Implements \(\sum_i x_i <= c\).

Parameters:

• domains (NDArray) – the domains of the variables, x is an alias for domains

• parameters (NDArray) – the parameters of the propagator, c is the first parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int

nucs.propagators.value_precede_propagator.compute_domains_value_precede(...) → int

Implements value precedence: whenever some x_i equals t, an earlier x_j equals s. Equivalently, the first occurrence of s comes before the first occurrence of t (or t does not occur).

The value t is forbidden in the prefix up to and including the first position whose domain still allows s (no s can occur strictly before it). Interior occurrences of t cannot be removed from NuCS interval domains, but such a violation is detected as soon as the variable is fixed to t.

Parameters:

• domains (NDArray) – the domains of the variables (the array x)

• parameters (NDArray) – the parameters, s is the first parameter, t is the second parameter

Returns:

the status of the propagation (consistency, inconsistency or entailment) as an int

Return type:

int