5.34. assign_and_counts
| DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- 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 of items of colour in each bin satisfies the condition .
- Example
-
FigureΒ 5.34.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.
Figure 5.34.1. Assignment of the items to the bins
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.
- Typical
- 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.
- Arg. properties
Contractible wrt. when .
Extensible wrt. when .
- 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
- Keywords
-
characteristic of a constraint: coloured, automaton, automaton with array of counters, derived collection.
- Derived Collection
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- 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.34.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.34.2. Initial and final graph of the constraint
(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.34.3 depicts the automaton associated with the constraint. To each attribute of the collection corresponds a 0-1 signature variable . The following signature constraint links and : . 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 , and finally imposes the condition .
Figure 5.34.3. Automaton of the constraint
