Global Constraint Catalog: Cindexed

5.192. indexed_sum

DESCRIPTION

LINKS

GRAPH

Origin

N. Beldiceanu

Constraint

$𝚒𝚗𝚍𝚎𝚡𝚎𝚍_𝚜𝚞𝚖 (𝙸𝚃𝙴𝙼𝚂, 𝚃𝙰𝙱𝙻𝙴)$

Arguments

$𝙸𝚃𝙴𝙼𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚠𝚎𝚒𝚐𝚑𝚝 - 𝚍𝚟𝚊𝚛)$
$𝚃𝙰𝙱𝙻𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛)$

Restrictions

| 𝙸𝚃𝙴𝙼𝚂 | > 0

| 𝚃𝙰𝙱𝙻𝙴 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙸𝚃𝙴𝙼𝚂, [𝚒𝚗𝚍𝚎𝚡, 𝚠𝚎𝚒𝚐𝚑𝚝])

𝙸𝚃𝙴𝙼𝚂 . 𝚒𝚗𝚍𝚎𝚡 \geq 1

𝙸𝚃𝙴𝙼𝚂 . 𝚒𝚗𝚍𝚎𝚡 \leq | 𝚃𝙰𝙱𝙻𝙴 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝙱𝙻𝙴, [𝚒𝚗𝚍𝚎𝚡, 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗])

𝚃𝙰𝙱𝙻𝙴 . 𝚒𝚗𝚍𝚎𝚡 \geq 1

𝚃𝙰𝙱𝙻𝙴 . 𝚒𝚗𝚍𝚎𝚡 \leq | 𝚃𝙰𝙱𝙻𝙴 |

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝚃𝙰𝙱𝙻𝙴, 𝚒𝚗𝚍𝚎𝚡)

Purpose

Given several items of the collection $𝙸𝚃𝙴𝙼𝚂$ (each of them having a specific fixed $𝚒𝚗𝚍𝚎𝚡$ as well as a $𝚠𝚎𝚒𝚐𝚑𝚝$ that may be negative or positive), and a table $𝚃𝙰𝙱𝙻𝙴$ (each entry of $𝚃𝙰𝙱𝙻𝙴$ corresponding to a $𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗$ variable), assign each item to an entry of $𝚃𝙰𝙱𝙻𝙴$ so that the sum of the weights of the items assigned to that entry is equal to the corresponding $𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗$ variable.

Example

(\begin{matrix} 〈\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 3 & 𝚠𝚎𝚒𝚐𝚑𝚝 - - 4, \\ 𝚒𝚗𝚍𝚎𝚡 - 1 & 𝚠𝚎𝚒𝚐𝚑𝚝 - 6, \\ 𝚒𝚗𝚍𝚎𝚡 - 3 & 𝚠𝚎𝚒𝚐𝚑𝚝 - 1 \end{matrix}〉, \\ 〈\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 1 & 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 - 6, \\ 𝚒𝚗𝚍𝚎𝚡 - 2 & 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 - 0, \\ 𝚒𝚗𝚍𝚎𝚡 - 3 & 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 - - 3 \end{matrix}〉 \end{matrix})

The $𝚒𝚗𝚍𝚎𝚡𝚎𝚍_𝚜𝚞𝚖$ constraint holds since the summation variables associated with each entry of $𝚃𝙰𝙱𝙻𝙴$ are equal to the sum of the weights of the items assigned to the corresponding entry:

$𝚃𝙰𝙱𝙻𝙴 [1] . 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 = 𝙸𝚃𝙴𝙼𝚂 [2] . 𝚠𝚎𝚒𝚐𝚑𝚝 = 6$ (since $𝚃𝙰𝙱𝙻𝙴 [1] . 𝚒𝚗𝚍𝚎𝚡 = 𝙸𝚃𝙴𝙼𝚂 [2] . 𝚒𝚗𝚍𝚎𝚡 = 1$ ),
$𝚃𝙰𝙱𝙻𝙴 [2] . 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 = 0$ (since $𝚃𝙰𝙱𝙻𝙴 [2] . 𝚒𝚗𝚍𝚎𝚡 = 2$ does not occur as a value of the $𝚒𝚗𝚍𝚎𝚡$ attribute of an item of $𝙸𝚃𝙴𝙼𝚂$ ),
$𝚃𝙰𝙱𝙻𝙴 [3] . 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗 = 𝙸𝚃𝙴𝙼𝚂 [1] . 𝚠𝚎𝚒𝚐𝚑𝚝 + 𝙸𝚃𝙴𝙼𝚂 [3] . 𝚠𝚎𝚒𝚐𝚑𝚝 = - 4 + 1 = - 3$ (since $𝚃𝙰𝙱𝙻𝙴 [3] . 𝚒𝚗𝚍𝚎𝚡 = 𝙸𝚃𝙴𝙼𝚂 [1] . 𝚒𝚗𝚍𝚎𝚡 = 𝙸𝚃𝙴𝙼𝚂 [3] . 𝚒𝚗𝚍𝚎𝚡 = 3$ ).

Typical

| 𝙸𝚃𝙴𝙼𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝙸𝚃𝙴𝙼𝚂 . 𝚒𝚗𝚍𝚎𝚡) > 1

| 𝚃𝙰𝙱𝙻𝙴 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝙱𝙻𝙴 . 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗) > 1

Symmetries

Items of $𝙸𝚃𝙴𝙼𝚂$ are permutable.
Items of $𝚃𝙰𝙱𝙻𝙴$ are permutable.

Reformulation

The $𝚒𝚗𝚍𝚎𝚡𝚎𝚍_𝚜𝚞𝚖$ $(𝙸𝚃𝙴𝙼𝚂, 𝚃𝙰𝙱𝙻𝙴)$ constraint can be expressed in term of a set of reified constraints and of $| 𝚃𝙰𝙱𝙻𝙴 |$ arithmetic constraints (i.e., $𝚜𝚌𝚊𝚕𝚊𝚛_𝚙𝚛𝚘𝚍𝚞𝚌𝚝$ constraints).

For each item $𝙸𝚃𝙴𝙼𝚂 [i]$ $(i \in [1, | 𝙸𝚃𝙴𝙼𝚂 |])$ and for each table entry $j$ $(j \in [1, | 𝚃𝙰𝙱𝙻𝙴 |])$ of $𝚃𝙰𝙱𝙻𝙴$ we create a 0-1 variable $B_{i j}$ that will be set to 1 if and only if $𝙸𝚃𝙴𝙼𝚂 [i] . 𝚒𝚗𝚍𝚎𝚡$ is fixed to $j$ (i.e., $B_{i j} \Leftrightarrow 𝙸𝚃𝙴𝙼𝚂 [i] . 𝚒𝚗𝚍𝚎𝚡 = j$ ).
For each entry $j$ of the table $𝚃𝙰𝙱𝙻𝙴$ , we impose the sum $𝙸𝚃𝙴𝙼𝚂 [1] . 𝚠𝚎𝚒𝚐𝚑𝚝 \cdot B_{1 j} + 𝙸𝚃𝙴𝙼𝚂 [2] . 𝚠𝚎𝚒𝚐𝚑𝚝 \cdot B_{2 j} + \dots + 𝙸𝚃𝙴𝙼𝚂 [| 𝙸𝚃𝙴𝙼𝚂 |] . 𝚠𝚎𝚒𝚐𝚑𝚝 \cdot B_{| 𝙸𝚃𝙴𝙼𝚂 | j}$ to be equal to $𝚃𝙰𝙱𝙻𝙴 [j] . 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗$ .

specialisation: $𝚋𝚒𝚗_𝚙𝚊𝚌𝚔𝚒𝚗𝚐$ (negative contribution not allowed, effective use variable for each bin replaced by an overall fixed capacity), $𝚋𝚒𝚗_𝚙𝚊𝚌𝚔𝚒𝚗𝚐_𝚌𝚊𝚙𝚊$ (negative contribution not allowed, effective use variable for each bin replaced by a fixed capacity for each bin).

used in graph description: $𝚜𝚞𝚖_𝚌𝚝𝚛$ .

Keywords

application area: assignment.

modelling: variable indexing, variable subscript.

For all items of $𝚃𝙰𝙱𝙻𝙴$ :

Arc input(s)

$𝙸𝚃𝙴𝙼𝚂$ $𝚃𝙰𝙱𝙻𝙴$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚝𝚎𝚖𝚜, 𝚝𝚊𝚋𝚕𝚎)

Arc arity

Arc constraint(s)

𝚒𝚝𝚎𝚖𝚜 . 𝚒𝚗𝚍𝚎𝚡 = 𝚝𝚊𝚋𝚕𝚎 . 𝚒𝚗𝚍𝚎𝚡

Sets

\begin{matrix} 𝖲𝖴𝖢𝖢 \mapsto \\ [\begin{matrix} 𝚜𝚘𝚞𝚛𝚌𝚎, \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 - 𝚌𝚘𝚕 (\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝙸𝚃𝙴𝙼𝚂 . 𝚠𝚎𝚒𝚐𝚑𝚝)] \end{matrix}) \end{matrix}] \end{matrix}

Constraint(s) on sets

𝚜𝚞𝚖_𝚌𝚝𝚛

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜, =, 𝚃𝙰𝙱𝙻𝙴 . 𝚜𝚞𝚖𝚖𝚊𝚝𝚒𝚘𝚗)

Graph model

We enforce the $𝚜𝚞𝚖_𝚌𝚝𝚛$ constraint on the weight of the items that are assigned to the same entry. Within the context of the Example slot, part (A) of Figure 5.192.1 shows the initial graphs associated with entries 1, 2 and 3 (i.e., one initial graph for each item of the $𝚃𝙰𝙱𝙻𝙴$ collection). Part (B) of Figure 5.192.1 shows the corresponding final graphs associated with entries 1 and 3. Each source vertex of the final graph can be interpreted as an item assigned to a specific entry of $𝚃𝙰𝙱𝙻𝙴$ .

Figure 5.192.1. Initial and final graph of the $𝚒𝚗𝚍𝚎𝚡𝚎𝚍_𝚜𝚞𝚖$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.192. indexed_sum

Figure 5.192.1. Initial and final graph of the 𝚒𝚗𝚍𝚎𝚡𝚎𝚍_𝚜𝚞𝚖 constraint

Figure 5.192.1. Initial and final graph of the $𝚒𝚗𝚍𝚎𝚡𝚎𝚍_𝚜𝚞𝚖$ constraint