## 5.327. sum_free

Origin
Constraint

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi }\right)$

Argument
 $\mathrm{\pi }$ $\mathrm{\pi \pi \pi \pi }$
Purpose

Impose for all pairs of values (not necessarily distinct) $i$, $j$ of the set $\mathrm{\pi }$ the fact that the sum $i+j$ is not an element of $\mathrm{\pi }$.

Example
$\left(\left\{1,3,5,9\right\}\right)$

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\left(\left\{1,3,5,9\right\}\right)$ constraint holds since:

• $1+1=2\beta \mathrm{\pi }$,Β Β  $1+3=4\beta \mathrm{\pi }$,Β Β  $1+5=6\beta \mathrm{\pi }$,Β Β  $1+9=10\beta \mathrm{\pi }$.

• $3+3=6\beta \mathrm{\pi }$,Β Β  $3+5=8\beta \mathrm{\pi }$,Β Β  $3+9=12\beta \mathrm{\pi }$.

• $5+5=10\beta \mathrm{\pi }$,Β Β  $5+9=14\beta \mathrm{\pi }$.

Usage

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ 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\beta €i\beta €n$), where ${x}_{i}$ corresponds to the subset in which element $i$ occurs. The constraints ($s\beta \left[1,k\right]$, $i,j\beta \left[1,n\right],i\beta €j,i+j\beta €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\beta €i\beta €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{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraints of the form $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\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{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint inΒ [HoeveSabharwal07].

Keywords