5.328. sum_of_weights_of_distinct_values

DESCRIPTIONLINKSGRAPH
Origin

[BeldiceanuCarlssonThiel02]

Constraint

πšœπšžπš–_𝚘𝚏_πš πšŽπš’πšπš‘πšπšœ_𝚘𝚏_πšπš’πšœπšπš’πš—πšŒπš_πšŸπšŠπš•πšžπšŽπšœ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚,π™²π™Ύπš‚πšƒ)

Synonym

𝚜𝚠𝚍𝚟.

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

All variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection take a value in the πš…π™°π™»πš„π™΄πš‚ collection. In addition π™²π™Ύπš‚πšƒ is the sum of the πš πšŽπš’πšπš‘πš attributes associated with the distinct values taken by the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
1,6,1,πšŸπšŠπš•-1πš πšŽπš’πšπš‘πš-5,πšŸπšŠπš•-2πš πšŽπš’πšπš‘πš-3,πšŸπšŠπš•-6πš πšŽπš’πšπš‘πš-7,12

The πšœπšžπš–_𝚘𝚏_πš πšŽπš’πšπš‘πšπšœ_𝚘𝚏_πšπš’πšœπšπš’πš—πšŒπš_πšŸπšŠπš•πšžπšŽπšœ constraint holds since its last argument π™²π™Ύπš‚πšƒ=12 is equal to the sum 5+7 of the weights of the values 1 and 6 that occur within the 〈1,6,1βŒͺ collection.

Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • All occurrences of two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped.

  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be renamed to any unused value.

See also

attached to cost variant: πš—πšŸπšŠπš•πšžπšŽΒ (all values have a weight of 1).

common keyword: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜, πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš πšŽπš’πšπš‘πšπšŽπš_πš™πšŠπš›πšπš’πšŠπš•_πšŠπš•πš•πšπš’πšπšΒ (weighted assignment).

Keywords

application area: assignment.

constraint type: relaxation.

filtering: cost filtering constraint.

problems: domination, weighted assignment, facilities location problem.

Arc input(s)

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

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πšŸπšŠπš•πšžπšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
β€’ ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
β€’ π’π”πŒ(πš…π™°π™»πš„π™΄πš‚,πš πšŽπš’πšπš‘πš)=π™²π™Ύπš‚πšƒ

Signature

Since we use the π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator, the number of sources of the final graph cannot exceed the number of sources of the initial graph. Since the initial graph contains |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| sources, this number is an upper bound of the number of sources of the final graph. Therefore we can rewrite ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| to ππ’πŽπ”π‘π‚π„β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| and simplify ππ’πŽπ”π‘π‚π„ Β― Μ² to ππ’πŽπ”π‘π‚π„ Β―.

PartsΒ (A) andΒ (B) of FigureΒ 5.328.1 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πŽπ”π‘π‚π„ graph property, the source vertices of the final graph are shown in a double circle. Since we also use the π’π”πŒ graph property we show the vertices from which we compute the total cost in a box.

Figure 5.328.1. Initial and final graph of the πšœπšžπš–_𝚘𝚏_πš πšŽπš’πšπš‘πšπšœ_𝚘𝚏_πšπš’πšœπšπš’πš—πšŒπš_πšŸπšŠπš•πšžπšŽπšœ constraint
ctrs/sum_of_weights_of_distinct_valuesActrs/sum_of_weights_of_distinct_valuesB
(a) (b)