Global Constraint Catalog: Csum_of_weights_of_distinct

5.388. sum_of_weights_of_distinct_values

DESCRIPTION

LINKS

GRAPH

Origin

[BeldiceanuCarlssonThiel02]

Constraint

$𝚜𝚞𝚖_𝚘𝚏_𝚠𝚎𝚒𝚐𝚑𝚝𝚜_𝚘𝚏_𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚟𝚊𝚕𝚞𝚎𝚜 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂, 𝙲𝙾𝚂𝚃)$

Synonym

$𝚜𝚠𝚍𝚟$ .

Arguments

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝙻𝚄𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝, 𝚠𝚎𝚒𝚐𝚑𝚝 - 𝚒𝚗𝚝)$
$𝙲𝙾𝚂𝚃$	$𝚍𝚟𝚊𝚛$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, [𝚟𝚊𝚕, 𝚠𝚎𝚒𝚐𝚑𝚝])

𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚠𝚎𝚒𝚐𝚑𝚝 \geq 0

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚒𝚗_𝚊𝚝𝚝𝚛

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝙲𝙾𝚂𝚃 \geq 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

(\begin{matrix} 〈1, 6, 1〉, \\ 〈\begin{matrix} 𝚟𝚊𝚕 - 1 & 𝚠𝚎𝚒𝚐𝚑𝚝 - 5, \\ 𝚟𝚊𝚕 - 2 & 𝚠𝚎𝚒𝚐𝚑𝚝 - 3, \\ 𝚟𝚊𝚕 - 6 & 𝚠𝚎𝚒𝚐𝚑𝚝 - 7 \end{matrix}〉, 12 \end{matrix})

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.

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚠𝚎𝚒𝚐𝚑𝚝) > 1

𝚖𝚊𝚡𝚟𝚊𝚕

(𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚠𝚎𝚒𝚐𝚑𝚝) > 0

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.

Arg. properties

Functional dependency: $𝙲𝙾𝚂𝚃$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .

See also

attached to cost variant: $𝚗𝚟𝚊𝚕𝚞𝚎$ (all values have a weight of 1).

common keyword: $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚠𝚒𝚝𝚑_𝚌𝚘𝚜𝚝𝚜$ , $𝚖𝚒𝚗𝚒𝚖𝚞𝚖_𝚠𝚎𝚒𝚐𝚑𝚝_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ , $𝚠𝚎𝚒𝚐𝚑𝚝𝚎𝚍_𝚙𝚊𝚛𝚝𝚒𝚊𝚕_𝚊𝚕𝚕𝚍𝚒𝚏𝚏$ (weighted assignment).

Keywords

application area: assignment.

constraint arguments: pure functional dependency.

constraint type: relaxation.

filtering: cost filtering constraint.

modelling: functional dependency.

problems: domination, weighted assignment, facilities location problem.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ $𝚅𝙰𝙻𝚄𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜, 𝚟𝚊𝚕𝚞𝚎𝚜)

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 $𝐍𝐒𝐎𝐔𝐑𝐂𝐄 \geq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ and simplify $\underset{̲}{\bar{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}}$ to $\bar{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$ .

Parts (A) and (B) of Figure 5.388.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.388.1. Initial and final graph of the $𝚜𝚞𝚖_𝚘𝚏_𝚠𝚎𝚒𝚐𝚑𝚝𝚜_𝚘𝚏_𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚟𝚊𝚕𝚞𝚎𝚜$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.388. sum_of_weights_of_distinct_values

Figure 5.388.1. Initial and final graph of the 𝚜𝚞𝚖_𝚘𝚏_𝚠𝚎𝚒𝚐𝚑𝚝𝚜_𝚘𝚏_𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚟𝚊𝚕𝚞𝚎𝚜 constraint

Figure 5.388.1. Initial and final graph of the $𝚜𝚞𝚖_𝚘𝚏_𝚠𝚎𝚒𝚐𝚑𝚝𝚜_𝚘𝚏_𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚟𝚊𝚕𝚞𝚎𝚜$ constraint