5.33. atmost1

DESCRIPTIONLINKS
Origin

[SadlerGervet01]

Constraint

πšŠπšπš–πš˜πšœπš1(πš‚π™΄πšƒπš‚)

Synonym

πš™πšŠπš’πš›_πšŠπšπš–πš˜πšœπš1.

Argument
πš‚π™΄πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜-πšœπšŸπšŠπš›,𝚌-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™΄πšƒπš‚,[𝚜,𝚌])
πš‚π™΄πšƒπš‚.𝚌β‰₯1
Purpose

Given a collection of set variables s 1 ,s 2 ,...,s n and their respective cardinality c 1 ,c 2 ,...,c n , the πšŠπšπš–πš˜πšœπš1 constraint enforces the following two conditions:

  • βˆ€i∈[1,n]:|s i |=c i ,

  • βˆ€i,j∈[1,n] (i<j): |s i β‹‚s j |≀1.

Example
𝚜-{5,8}𝚌-2,𝚜-{5}𝚌-1,𝚜-{5,6,7}𝚌-3,𝚜-{1,4}𝚌-2

The πšŠπšπš–πš˜πšœπš1 constraint holds since:

  • |{5,8}|=2, |{5}|=1, |{5,6,7}|=3, |{1,4}|=2.

  • |{5,8}β‹‚{5}|≀1, |{5,8}β‹‚{5,6,7}|≀1, |{5,8}β‹‚{1,4}|≀1,

    |{5}β‹‚{5,6,7}|≀1, |{5}β‹‚{1,4}|≀1,

    |{5,6,7}β‹‚{1,4}|≀1.

Typical
|πš‚π™΄πšƒπš‚|>1
Symmetries
  • Items of πš‚π™΄πšƒπš‚ are permutable.

  • All occurrences of two distinct values of πš‚π™΄πšƒπš‚.𝚜 can be swapped; all occurrences of a value of πš‚π™΄πšƒπš‚.𝚜 can be renamed to any unused value.

Remark

When we have only two set variables the πšŠπšπš–πš˜πšœπš1 constraint was called πš™πšŠπš’πš›_πšŠπšπš–πš˜πšœπš1 inΒ [HoeveSabharwal07].

Algorithm

C.Β BessiΓ¨re etΒ al. have shown inΒ [BessiereHebrardHnichWalsh04] that it is NP -hard to enforce bound consistency for the πšŠπšπš–πš˜πšœπš1 constraint. Consequently, following the first filtering algorithm from A.Β Sadler and C.Β GervetΒ [SadlerGervet01], W.-J.Β vanΒ Hoeve and A.Β Sabharwal have proposed an algorithm that enforces bound-consistency when the πšŠπšπš–πš˜πšœπš1 constraint involves only two sets variablesΒ [HoeveSabharwal07].

Keywords

constraint arguments: constraint involving set variables.

constraint type: predefined constraint.

filtering: bound-consistency.