5.182. k_used_by

DESCRIPTIONLINKSGRAPH
Origin

Derived from 𝚞𝚜𝚎𝚍_πš‹πš’

Constraint

πš”_𝚞𝚜𝚎𝚍_πš‹πš’(πš‚π™΄πšƒπš‚)

Type
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Argument
πš‚π™΄πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
|πš‚π™΄πšƒπš‚|>1
πš—πš˜πš—_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš’πš£πšŽ(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
Purpose

Given |πš‚π™΄πšƒπš‚| sets of domain variables, the πš”_𝚞𝚜𝚎𝚍_πš‹πš’ constraint enforces a 𝚞𝚜𝚎𝚍_πš‹πš’ constraint between each pair of consecutive sets.

Example
𝚜𝚎𝚝-πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-5,πšŸπšŠπš›-2,πšŸπšŠπš›-1,𝚜𝚎𝚝-πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-5,𝚜𝚎𝚝-1,1,2,5

The πš”_𝚞𝚜𝚎𝚍_πš‹πš’ constraint holds since:

  • The multiset of values {{1,1,1,2,5,9}} associated with the second collection of variables is included into the multiset {{1,1,1,2,5,9}} associated with the first collection of variables.

  • The multiset of values {{1,1,2,5}} associated with the third collection of variables is included into the multiset {{1,1,1,2,5,9}} associated with the second collection of variables.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
Symmetries
  • Items of πš‚π™΄πšƒπš‚ are permutable.

  • 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

Similarly to the πš”_πšœπšŠπš–πšŽ constraintΒ [ElbassioniKatrielKutzMahajan05], finding out whether the πš”_𝚞𝚜𝚎𝚍_πš‹πš’ constraint has a solution or not is NP-hard when we have more than one 𝚞𝚜𝚎𝚍_πš‹πš’ constraint.

See also

common keyword: πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•, πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš–πš˜πšπšžπš•πš˜, πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (system of constraints).

implied by: πš”_πšœπšŠπš–πšŽ.

part of system of constraints: 𝚞𝚜𝚎𝚍_πš‹πš’.

used in graph description: 𝚞𝚜𝚎𝚍_πš‹πš’.

Keywords

combinatorial object: multiset.

constraint type: system of constraints, decomposition.

modelling: inclusion.

Arc input(s)

πš‚π™΄πšƒπš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝1,𝚜𝚎𝚝2)

Arc arity
Arc constraint(s)
𝚞𝚜𝚎𝚍_πš‹πš’(𝚜𝚎𝚝1.𝚜𝚎𝚝,𝚜𝚎𝚝2.𝚜𝚎𝚝)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš‚π™΄πšƒπš‚|-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.182.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a 𝚞𝚜𝚎𝚍_πš‹πš’ constraint.

Figure 5.182.1. Initial and final graph of the πš”_𝚞𝚜𝚎𝚍_πš‹πš’ constraint
ctrs/k_used_byActrs/k_used_byB
(a) (b)