5.172. inverse_set

DESCRIPTIONLINKSGRAPH
Origin

Derived from πš’πš—πšŸπšŽπš›πšœπšŽ.

Constraint

πš’πš—πšŸπšŽπš›πšœπšŽ_𝚜𝚎𝚝(πš‡,𝚈)

Arguments
πš‡πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚎𝚝-πšœπšŸπšŠπš›)
πšˆπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚎𝚝-πšœπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš‡,[πš’πš—πšπšŽπš‘,𝚜𝚎𝚝])
πš›πšŽπššπšžπš’πš›πšŽπš(𝚈,[πš’πš—πšπšŽπš‘,𝚜𝚎𝚝])
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(πš‡,πš’πš—πšπšŽπš‘)
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(𝚈,πš’πš—πšπšŽπš‘)
πš‡.πš’πš—πšπšŽπš‘β‰₯1
πš‡.πš’πš—πšπšŽπš‘β‰€|πš‡|
𝚈.πš’πš—πšπšŽπš‘β‰₯1
𝚈.πš’πš—πšπšŽπš‘β‰€|𝚈|
πš‡.𝚜𝚎𝚝β‰₯1
πš‡.πšœπšŽπšβ‰€|𝚈|
𝚈.𝚜𝚎𝚝β‰₯1
𝚈.πšœπšŽπšβ‰€|πš‡|
Purpose

The following two statements are equivalent:

  1. Value j belongs to the set variable of the i th item of the πš‡ collection.

  2. Value i belongs to the set variable of the j th item of the 𝚈 collection.

I.e.,Β jβˆˆπš‡[i]⇔i∈𝚈[j].

Example
πš’πš—πšπšŽπš‘-1𝚜𝚎𝚝-{2,4},πš’πš—πšπšŽπš‘-2𝚜𝚎𝚝-{4},πš’πš—πšπšŽπš‘-3𝚜𝚎𝚝-{1},πš’πš—πšπšŽπš‘-4𝚜𝚎𝚝-{4},πš’πš—πšπšŽπš‘-1𝚜𝚎𝚝-{3},πš’πš—πšπšŽπš‘-2𝚜𝚎𝚝-{1},πš’πš—πšπšŽπš‘-3𝚜𝚎𝚝-βˆ…,πš’πš—πšπšŽπš‘-4𝚜𝚎𝚝-{1,2,4},πš’πš—πšπšŽπš‘-5𝚜𝚎𝚝-βˆ…

The πš’πš—πšŸπšŽπš›πšœπšŽ_𝚜𝚎𝚝 constraint holds since:

2βˆˆπš‡[1].πšœπšŽπšβ‡”1∈𝚈[2].𝚜𝚎𝚝,4βˆˆπš‡[1].πšœπšŽπšβ‡”1∈𝚈[4].𝚜𝚎𝚝,4βˆˆπš‡[2].πšœπšŽπšβ‡”2∈𝚈[4].𝚜𝚎𝚝,1βˆˆπš‡[3].πšœπšŽπšβ‡”3∈𝚈[1].𝚜𝚎𝚝,4βˆˆπš‡[4].πšœπšŽπšβ‡”4∈𝚈[4].𝚜𝚎𝚝.

Typical
|πš‡|>1
|𝚈|>1
Symmetries
Usage

The πš’πš—πšŸπšŽπš›πšœπšŽ_𝚜𝚎𝚝 constraint can for instance be used in order to model problems where one has to place items on a rectangular board in such a way that a column or a row can have more than one item. We have one set variable for each row of the board; Its values are the column indexes corresponding to the positions where an item is placed. Similarly we have also one set variable for each column of the board; Its values are the row indexes corresponding to the positions where an item is placed. The πš’πš—πšŸπšŽπš›πšœπšŽ_𝚜𝚎𝚝 constraint maintains the link between the rows and the columns variables. FigureΒ 5.172.1 shows the board that can be associated with the example of the Example slot.

Figure 5.172.1. Board associated with the example of the Example slot
ctrs/inverse_set1
Systems

inverseSet in Choco.

See also

common keyword: πš’πš—πšŸπšŽπš›πšœπšŽ_πš πš’πšπš‘πš’πš—_πš›πšŠπš—πšπšŽΒ (channelling constraint).

specialisation: πš’πš—πšŸπšŽπš›πšœπšŽΒ (𝚜𝚎𝚝 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšπš˜πš–πšŠπš’πš— πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

constraint arguments: constraint involving set variables.

modelling: channelling constraint, set channel, dual model.

Arc input(s)

πš‡ 𝚈

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚑,𝚒)

Arc arity
Arc constraint(s)
πš’πš—_𝚜𝚎𝚝(𝚒.πš’πš—πšπšŽπš‘,𝚑.𝚜𝚎𝚝)β‡”πš’πš—_𝚜𝚎𝚝(𝚑.πš’πš—πšπšŽπš‘,𝚒.𝚜𝚎𝚝)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš‡|*|𝚈|

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.172.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.172.2. Initial and final graph of the πš’πš—πšŸπšŽπš›πšœπšŽ_𝚜𝚎𝚝 constraint
ctrs/inverse_setActrs/inverse_setB
(a) (b)