5.327. sum_free

DESCRIPTIONLINKS
Origin

[HoeveSabharwal07]

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βˆ‰πš‚,Β Β  1+3=4βˆ‰πš‚,Β Β  1+5=6βˆ‰πš‚,Β Β  1+9=10βˆ‰πš‚.

  • 3+3=6βˆ‰πš‚,Β Β  3+5=8βˆ‰πš‚,Β Β  3+9=12βˆ‰πš‚.

  • 5+5=10βˆ‰πš‚,Β Β  5+9=14βˆ‰πš‚.

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≀i≀n), where x i corresponds to the subset in which element i occurs. The constraints x i =s∧x j =sβ‡’x i+j β‰ s (s∈[1,k], i,j∈[1,n],i≀j,i+j≀n) enforce that the k subsets are sum -free. We have O(kΒ·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≀i≀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.