5.299. open_global_cardinality_low_up

DESCRIPTIONLINKSGRAPH
Origin

[HoeveRegin06]

Constraint

πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™(πš‚,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Arguments
πš‚πšœπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš,πš˜πš–πš’πš—-πš’πš—πš,πš˜πš–πšŠπš‘-πš’πš—πš)
Restrictions
πš‚β‰₯1
πš‚β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°π™»πš„π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš•,πš˜πš–πš’πš—,πš˜πš–πšŠπš‘])
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰₯0
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰€πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘
Purpose

Each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• (1≀i≀|πš…π™°π™»πš„π™΄πš‚|) should be taken by at least πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πš’πš— and at most πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πšŠπš‘ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection for which the corresponding position belongs to the set πš‚. Positions are numbered from 1.

Example
{2,3,4},3,3,8,6,πšŸπšŠπš•-3πš˜πš–πš’πš—-1πš˜πš–πšŠπš‘-3,πšŸπšŠπš•-5πš˜πš–πš’πš—-0πš˜πš–πšŠπš‘-1,πšŸπšŠπš•-6πš˜πš–πš’πš—-1πš˜πš–πšŠπš‘-2

The πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint holds since:

  • Values 3, 5 and 6 are respectively used 1 (1≀1≀3), 0 (0≀0≀1) and 1 (1≀1≀2) times within the collection 〈3,3,8,6βŒͺ (the first item 3 of 〈3,3,8,6βŒͺ is ignored since value 1 does not belong to the first argument S={2,3,4} of the πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint).

  • No constraint was specified for value 8.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°π™»πš„π™΄πš‚|>1
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘>0
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be replaced by any other value that also does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•.

Usage

In their articleΒ [HoeveRegin06], W.-J.Β vanΒ Hoeve and J.-C.Β RΓ©gin motivate the πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint by the following scheduling problem. Consider a set of activities (where each activity has a fixed duration 1 and a start variable) that can be processed on two factory lines such that all the activities that will be processed on a given line must be pairwise distinct. This can be modelled by using one πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint for each line, involving all the start variables as well as a set variable whose final value specifies the set of activities assigned to that specific factory line.

Note that this can also be directly modelled by a single πšπš’πšπšπš— constraint. This is done by introducing an assignment variable for each activity. The initial domain of each assignment variable consists of two values that respectively correspond to the two factory lines.

Algorithm

A slight adaptation of the flow model that handles the original πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraintΒ [Regin96] is described inΒ [HoeveRegin06].

See also

common keyword: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (assignment,counting constraint).

generalisation: πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (πšπš’πš‘πšŽπš πš’πš—πšπšŽπš›πšŸπšŠπš• replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

hard version: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™.

specialisation: πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (each active valueAn active value corresponds to a value occuring at a position mentionned in the set πš‚. should occur at most once).

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

Keywords

application area: assignment.

constraint arguments: constraint involving set variables.

constraint type: open constraint, value constraint, counting constraint.

filtering: flow.

For all items of πš…π™°π™»πš„π™΄πš‚:

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•
β€’ πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’,πš‚)
Graph property(ies)
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—
β€’ ππ•π„π‘π“π„π—β‰€πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘

Graph model

Since we want to express one unary constraint for each value we use the β€œFor all items of πš…π™°π™»πš„π™΄πš‚β€ iterator. The only difference with the graph model of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint is the arc constraint where we also specify that the position of the considered variable should belong to the first argument πš‚.

PartΒ (A) of FigureΒ 5.299.1 shows the initial graphs associated with each value 3, 5 and 6 of the πš…π™°π™»πš„π™΄πš‚ collection of the Example slot. PartΒ (B) of FigureΒ 5.299.1 shows the two corresponding final graphs respectively associated with values 3 and 6 that are both assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection (since value 5 is not assigned to any variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection the final graph associated with value 5 is empty). Since we use the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 graph property, the vertices of the final graphs are stressed in bold.

Figure 5.299.1. Initial and final graph of the πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint
ctrs/open_global_cardinality_low_upActrs/open_global_cardinality_low_upB
(a) (b)