## 5.386. sum_free

Origin
Constraint

$\mathrm{𝚜𝚞𝚖}_\mathrm{𝚏𝚛𝚎𝚎}\left(𝚂\right)$

Argument
 $𝚂$ $\mathrm{𝚜𝚟𝚊𝚛}$
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
$\left(\left\{1,3,5,9\right\}\right)$

The $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚏𝚛𝚎𝚎}$$\left(\left\{1,3,5,9\right\}\right)$ 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 $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚏𝚛𝚎𝚎}$ 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\le i\le n$), where ${x}_{i}$ corresponds to the subset in which element $i$ occurs. The constraints ${x}_{i}=s\wedge {x}_{j}=s⇒{x}_{i+j}\ne s$ ($s\in \left[1,k\right]$, $i,j\in \left[1,n\right],i\le j,i+j\le n$) enforce that the $k$ subsets are sum-free. We have $O\left(k·{n}^{2}\right)$ 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\le i\le 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$ $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚏𝚛𝚎𝚎}$ constraints of the form $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚏𝚛𝚎𝚎}$$\left({S}_{i}\right)$.

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 $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚏𝚛𝚎𝚎}$ constraint in [HoeveSabharwal07].

Keywords