5.27. assign_and_counts

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ(π™²π™Ύπ™»π™Ύπš„πšπš‚,π™Έπšƒπ™΄π™Όπš‚,πšπ™΄π™»π™Ύπ™Ώ,π™»π™Έπ™Όπ™Έπšƒ)

Arguments
π™²π™Ύπ™»π™Ύπš„πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
π™Έπšƒπ™΄π™Όπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš‹πš’πš—-πšπšŸπšŠπš›,πšŒπš˜πš•πš˜πšžπš›-πšπšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™ΏπšŠπšπš˜πš–
π™»π™Έπ™Όπ™ΈπšƒπšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™²π™Ύπ™»π™Ύπš„πšπš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(π™²π™Ύπ™»π™Ύπš„πšπš‚,πšŸπšŠπš•)
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Όπš‚,[πš‹πš’πš—,πšŒπš˜πš•πš˜πšžπš›])
πšπ™΄π™»π™Ύπ™Ώβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Given several items (each of them having a specific colour that may not be initially fixed), and different bins, assign each item to a bin, so that the total number n of items of colour π™²π™Ύπ™»π™Ύπš„πšπš‚ in each bin satisfies the condition n πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ.

Example
4,πš‹πš’πš—-1πšŒπš˜πš•πš˜πšžπš›-4,πš‹πš’πš—-3πšŒπš˜πš•πš˜πšžπš›-4,πš‹πš’πš—-1πšŒπš˜πš•πš˜πšžπš›-4,πš‹πš’πš—-1πšŒπš˜πš•πš˜πšžπš›-5,≀,2

FigureΒ 5.27.1 shows the solution associated with the example. The items and the bins are respectively represented by little squares and by the different columns. Each little square contains the value of the πš”πšŽπš’ attribute of the item to which it corresponds. The items for which the colour attribute is equal to 4 are located under the thick line. The πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ constraint holds since for each used bin (i.e.,Β namely bins 1 and 3) the number of assigned items for which the colour attribute is equal to 4 is less than or equal to the limit 2.

Figure 5.27.1. Assignment of the items to the bins
ctrs/assign_and_counts1
Typical
|π™²π™Ύπ™»π™Ύπš„πšπš‚|>0
|π™Έπšƒπ™΄π™Όπš‚|>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš‹πš’πš—)>1
π™»π™Έπ™Όπ™Έπšƒ>0
π™»π™Έπ™Όπ™Έπšƒ<|π™Έπšƒπ™΄π™Όπš‚|
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.

Usage

Some persons have pointed out that it is impossible to use constraints such as πšŠπš–πš˜πš—πš, πšŠπšπš•πšŽπšŠπšœπš, πšŠπšπš–πš˜πšœπš, πšŒπš˜πšžπš—πš, or πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ if the set of variables is not initially known. However, this is for instance required in practice for some timetabling problems.

See also

assignment dimension removed: πšŒπš˜πšžπš—πš, πšŒπš˜πšžπš—πšπšœ.

used in graph description: πšŒπš˜πšžπš—πšπšœ.

Keywords

application area: assignment.

characteristic of a constraint: coloured, automaton, automaton with array of counters, derived collection.

final graph structure: acyclic, bipartite, no loop.

modelling: assignment dimension.

Derived Collection
πšŒπš˜πš•(πš…π™°π™»πš„π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš),[πš’πšπšŽπš–(πšŸπšŠπš•-π™²π™Ύπ™»π™Ύπš„πšπš‚.πšŸπšŠπš•)])
Arc input(s)

π™Έπšƒπ™΄π™Όπš‚ π™Έπšƒπ™΄π™Όπš‚

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

Arc arity
Arc constraint(s)
πš’πšπšŽπš–πšœ1.πš‹πš’πš—=πš’πšπšŽπš–πšœ2.πš‹πš’πš—
Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Sets
π–²π–΄π–’π–’β†¦πšœπš˜πšžπš›πšŒπšŽ,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-π™Έπšƒπ™΄π™Όπš‚.πšŒπš˜πš•πš˜πšžπš›)]

Constraint(s) on sets
πšŒπš˜πšžπš—πšπšœ(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πšπ™΄π™»π™Ύπ™Ώ,π™»π™Έπ™Όπ™Έπšƒ)
Graph model

We enforce the πšŒπš˜πšžπš—πšπšœ constraint on the colour of the items that are assigned to the same bin.

PartsΒ (A) andΒ (B) of FigureΒ 5.27.2 respectively show the initial and final graph associated with the Example slot. The final graph consists of the following two connected components:

  • The connected component containing six vertices corresponds to the items that are assigned to bin 1.

  • The connected component containing two vertices corresponds to the items that are assigned to bin 3.

Figure 5.27.2. Initial and final graph of the πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ constraint
ctrs/assign_and_countsActrs/assign_and_countsB
(a) (b)

The πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ constraint holds since for each set of successors of the vertices of the final graph no more than two items take colour 4.

Automaton

FigureΒ 5.27.3 depicts the automaton associated with the πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ constraint. To each πšŒπš˜πš•πš˜πšžπš› attribute π™²π™Ύπ™»π™Ύπš„πš i of the collection π™Έπšƒπ™΄π™Όπš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links π™²π™Ύπ™»π™Ύπš„πš i and πš‚ i : π™²π™Ύπ™»π™Ύπš„πš i βˆˆπ™²π™Ύπ™»π™Ύπš„πšπš‚β‡”πš‚ i . For all items of the collection π™Έπšƒπ™΄π™Όπš‚ for which the πšŒπš˜πš•πš˜πšžπš› attribute takes its value in π™²π™Ύπ™»π™Ύπš„πšπš‚, counts for each value assigned to the πš‹πš’πš— attribute its number of occurrences n, and finally imposes the condition n πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ.

Figure 5.27.3. Automaton of the πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ constraint
ctrs/assign_and_counts2