Global Constraint Catalog: Csum

5.386. sum_free

DESCRIPTION

LINKS

Origin

Constraint

$𝚜𝚞𝚖_𝚏𝚛𝚎𝚎 (𝚂)$

Argument

𝚂

𝚜𝚟𝚊𝚛

Purpose

Impose for all pairs of values (not necessarily distinct) $i$ , $j$ of the set $𝚂$ the fact that the sum $i + j$ is not an element of $𝚂$ .

Example

({1, 3, 5, 9})

The $𝚜𝚞𝚖_𝚏𝚛𝚎𝚎$ $({1, 3, 5, 9})$ constraint holds since:

$1 + 1 = 2 \notin 𝚂$ , $1 + 3 = 4 \notin 𝚂$ , $1 + 5 = 6 \notin 𝚂$ , $1 + 9 = 10 \notin 𝚂$ .
$3 + 3 = 6 \notin 𝚂$ , $3 + 5 = 8 \notin 𝚂$ , $3 + 9 = 12 \notin 𝚂$ .
$5 + 5 = 10 \notin 𝚂$ , $5 + 9 = 14 \notin 𝚂$ .

Usage

The $𝚜𝚞𝚖_𝚏𝚛𝚎𝚎$ constraint was introduced by W.-J. van Hoeve and A. Sabharwal in order to model in a concise way Schur problems.

On one hand, the first model has $n$ domain variables $x_{i}$ ( $1 \leq i \leq n$ ), where $x_{i}$ corresponds to the subset in which element $i$ occurs. The constraints $x_{i} = s \land x_{j} = s \Rightarrow x_{i + j} \neq s$ ( $s \in [1, k]$ , $i, j \in [1, n], i \leq j, i + j \leq n$ ) enforce that the $k$ subsets are sum-free. We have $O (k \cdot n^{2})$ such constraints.
On the other hand, the model proposed by W.-J. van Hoeve and A. Sabharwal represents in an explicit way with a set variable $S_{i}$ ( $1 \leq i \leq n$ ) each subset of the partition we are looking for. Now, to express the fact that these $k$ subsets are sum-free they simply use $k$ $𝚜𝚞𝚖_𝚏𝚛𝚎𝚎$ constraints of the form $𝚜𝚞𝚖_𝚏𝚛𝚎𝚎$ $(S_{i})$ .

While the two models have the same behaviour when we focus on the number of backtracks the second model is much more efficient from a memory point of view.

Algorithm

W.-J. van Hoeve and A. Sabharwal have proposed an algorithm that enforces bound-consistency for the $𝚜𝚞𝚖_𝚏𝚛𝚎𝚎$ constraint in [HoeveSabharwal07].

Keywords

constraint arguments: unary constraint, constraint involving set variables.

constraint type: predefined constraint.

filtering: bound-consistency.

problems: Schur number.

Global Constraint Catalog

5. Global Constraint Catalogue

5.386. sum_free