5.28. assign_and_nvalues

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœ and πš—πšŸπšŠπš•πšžπšŽπšœ.

Constraint

πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πš—πšŸπšŠπš•πšžπšŽπšœ(π™Έπšƒπ™΄π™Όπš‚,πšπ™΄π™»π™Ύπ™Ώ,π™»π™Έπ™Όπ™Έπšƒ)

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

Example
πš‹πš’πš—-2πšŸπšŠπš•πšžπšŽ-3,πš‹πš’πš—-1πšŸπšŠπš•πšžπšŽ-5,πš‹πš’πš—-2πšŸπšŠπš•πšžπšŽ-3,πš‹πš’πš—-2πšŸπšŠπš•πšžπšŽ-3,πš‹πš’πš—-2πšŸπšŠπš•πšžπšŽ-4,≀,2

FigureΒ 5.28.1 depicts the solution corresponding to the example. The πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πš—πšŸπšŠπš•πšžπšŽπšœ 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.

Figure 5.28.1. An assignment with at most two distinct values in parallel
ctrs/assign_and_nvalues1
Typical
|π™Έπšƒπ™΄π™Όπš‚|>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš‹πš’πš—)>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πšŸπšŠπš•πšžπšŽ)>1
π™»π™Έπ™Όπ™Έπšƒ>1
π™»π™Έπ™Όπ™Έπšƒ<|π™Έπšƒπ™΄π™Όπš‚|
Symmetries
  • 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

Let us give two examples where the πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πš—πšŸπšŠπš•πšžπšŽπšœ 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.

See also

assignment dimension removed: πš—πšŸπšŠπš•πšžπšŽ, πš—πšŸπšŠπš•πšžπšŽπšœ.

common keyword: πš—πšŸπšŠπš•πšžπšŽπšœ_πšŽπš‘πšŒπšŽπš™πš_0Β (number of distinct values).

related: πš›πš˜πš˜πšπšœ.

used in graph description: πš—πšŸπšŠπš•πšžπšŽπšœ.

Keywords

application area: assignment.

final graph structure: acyclic, bipartite, no loop.

modelling: assignment dimension, number of distinct values.

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 items that are assigned to the same bin.

PartsΒ (A) andΒ (B) of FigureΒ 5.28.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.

Figure 5.28.2. Initial and final graph of the πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πš—πšŸπšŠπš•πšžπšŽπšœ constraint
ctrs/assign_and_nvaluesActrs/assign_and_nvaluesB
(a) (b)

The πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πš—πšŸπšŠπš•πšžπšŽπšœ 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.