An 0(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization

摘要

This paper gives an 0(n log n) bound-consistency filtering algorithm for the conjunction alldifferent(V_0, V_1,..., V_(n-1)) ∧ f(V_0) ⊕ f(V_1) ⊕ … ⊕ f(V_(n-1)) ≤ cst, (V_0, V_1, … , V_(1-1), cst ∈ N~+), where (N, ⊕) is a commutative group, f is a unary function, and both ⊕ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.