## 5.35. assign_and_nvalues

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi },\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ},\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\right)$

Arguments
 $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$ $\mathrm{\pi \pi \pi \pi }$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi },\left[\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi }\right]\right)$
Purpose

Given several items (each of them having a specific value that may not be initially fixed), and different bins, assign each item to a bin, so that the number $n$ of distinct values in each bin satisfies the condition $n\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$.

Example
$\left(\begin{array}{c}β©\begin{array}{cc}\mathrm{\pi \pi \pi }-2\hfill & \mathrm{\pi \pi \pi \pi \pi }-3,\hfill \\ \mathrm{\pi \pi \pi }-1\hfill & \mathrm{\pi \pi \pi \pi \pi }-5,\hfill \\ \mathrm{\pi \pi \pi }-2\hfill & \mathrm{\pi \pi \pi \pi \pi }-3,\hfill \\ \mathrm{\pi \pi \pi }-2\hfill & \mathrm{\pi \pi \pi \pi \pi }-3,\hfill \\ \mathrm{\pi \pi \pi }-2\hfill & \mathrm{\pi \pi \pi \pi \pi }-4\hfill \end{array}βͺ,\beta €,2\hfill \end{array}\right)$

FigureΒ 5.35.1 depicts the solution corresponding to the example.

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint holds since for each used bin (i.e.,Β namely bins 1 and 2) the number of distinct colours of the corresponding assigned items is less than or equal to the limit 2.

Typical
 $|\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi }\right)>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi \pi \pi }\right)>1$ $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[<,\beta €\right]$ $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }>1$ $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }<|\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }|$
Symmetries
• Items of $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ are permutable.

• All occurrences of two distinct values of $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi }$ can be swapped; all occurrences of a value of $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi }$ can be renamed to any unused value.

Arg. properties
• Contractible wrt. $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ when $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[<,\beta €\right]$.

• Extensible wrt. $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ when $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[\beta ₯,>\right]$.

Usage

Let us give two examples where the $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint is useful:

• Quite often, in bin-packing problems, each item has a specific type, and one wants to assign items of similar type to each bin.

• In a vehicle routing problem, one wants to restrict the number of towns visited by each vehicle. Note that several customers may be located at the same town. In this example, each bin would correspond to a vehicle, each item would correspond to a visit to a customer, and the colour of an item would be the location of the corresponding customer.

Keywords
Arc input(s)

$\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$

Arc generator
$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$
Graph class
 $\beta ’$$\mathrm{\pi °\pi ²\pi \pi ²\pi »\pi Έ\pi ²}$ $\beta ’$$\mathrm{\pi ±\pi Έ\pi Ώ\pi °\pi \pi \pi Έ\pi \pi ΄}$ $\beta ’$$\mathrm{\pi ½\pi Ύ}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ}$

Sets
$\begin{array}{c}\mathrm{\pi ²\pi ΄\pi ’\pi ’}\beta ¦\hfill \\ \left[\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi \pi },\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi }\left(\begin{array}{c}\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }-\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right),\hfill \\ \mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi \pi \pi }\right)\right]\hfill \end{array}\right)\hfill \end{array}\right]\hfill \end{array}$

Constraint(s) on sets
$\mathrm{\pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ},\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\right)$
Graph model

We enforce the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint on the items that are assigned to the same bin.

PartsΒ (A) andΒ (B) of FigureΒ 5.35.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 8 vertices corresponds to the items that are assigned to bin 2.

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

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint holds since for each set of successors of the vertices of the final graph no more than two distinct values are used:

• The unique item assigned to bin 1 uses value 5.

• Items assigned to bin 2 use values 3 and 4.