## 5.383. sum

Origin
Constraint

$\mathrm{𝚜𝚞𝚖}$$\left(\mathrm{𝙸𝙽𝙳𝙴𝚇},\mathrm{𝚂𝙴𝚃𝚂},\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂},𝚂\right)$

Synonym

$\mathrm{𝚜𝚞𝚖}_\mathrm{𝚙𝚛𝚎𝚍}$.

Arguments
 $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚂𝙴𝚃𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚎𝚝}-\mathrm{𝚜𝚒𝚗𝚝}\right)$ $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚌𝚜𝚝}-\mathrm{𝚒𝚗𝚝}\right)$ $𝚂$ $\mathrm{𝚍𝚟𝚊𝚛}$
Restrictions
 $|\mathrm{𝚂𝙴𝚃𝚂}|\ge 1$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚂𝙴𝚃𝚂},\left[\mathrm{𝚒𝚗𝚍},\mathrm{𝚜𝚎𝚝}\right]\right)$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝚂𝙴𝚃𝚂},\mathrm{𝚒𝚗𝚍}\right)$ $|\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}|\ge 1$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂},\mathrm{𝚌𝚜𝚝}\right)$
Purpose

$𝚂$ is equal to the sum of the constants of $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$ corresponding to the ${\mathrm{𝙸𝙽𝙳𝙴𝚇}}^{th}$ set of the $\mathrm{𝚂𝙴𝚃𝚂}$ collection.

Example
$\left(\begin{array}{c}8,〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍}-8\hfill & \mathrm{𝚜𝚎𝚝}-\left\{2,3\right\},\hfill \\ \mathrm{𝚒𝚗𝚍}-1\hfill & \mathrm{𝚜𝚎𝚝}-\left\{3\right\},\hfill \\ \mathrm{𝚒𝚗𝚍}-3\hfill & \mathrm{𝚜𝚎𝚝}-\left\{1,4,5\right\},\hfill \\ \mathrm{𝚒𝚗𝚍}-6\hfill & \mathrm{𝚜𝚎𝚝}-\left\{2,4\right\}\hfill \end{array}〉,\hfill \\ 〈4,9,1,3,1〉,10\hfill \end{array}\right)$

The $\mathrm{𝚜𝚞𝚖}$ constraint holds since its last argument $𝚂=10$ is equal to the sum of the 2th and 3th items of the collection $〈4,9,1,3,1〉$. As illustrated by Figure 5.383.1, this stems from the fact that its first argument $\mathrm{𝙸𝙽𝙳𝙴𝚇}=8$ corresponds to the value of the $\mathrm{𝚒𝚗𝚍}$ attribute of the first item of the $\mathrm{𝚂𝙴𝚃𝚂}$ collection. Consequently the corresponding set $\left\{2,3\right\}$ is used for summing the 2th and 3th items of the $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$ collection.

Typical
 $|\mathrm{𝚂𝙴𝚃𝚂}|>1$ $|\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}|>|\mathrm{𝚂𝙴𝚃𝚂}|$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}.\mathrm{𝚌𝚜𝚝}\right)>1$
Symmetry

Items of $\mathrm{𝚂𝙴𝚃𝚂}$ are permutable.

Arg. properties

Functional dependency: $𝚂$ determined by $\mathrm{𝙸𝙽𝙳𝙴𝚇}$, $\mathrm{𝚂𝙴𝚃𝚂}$ and $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$.

Usage

In his article introducing the $\mathrm{𝚜𝚞𝚖}$ constraint, Tallys H. Yunes mentions the Sequence Dependent Cumulative Cost Problem as the subproblem that originally motivates this constraint.

Remark

The $\mathrm{𝚜𝚞𝚖}$ constraint is called $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚙𝚛𝚎𝚍}$ in MiniZinc (http://www.minizinc.org/).

Algorithm

The article [Yunes02] gives the convex hull relaxation of the $\mathrm{𝚜𝚞𝚖}$ constraint.

Systems
Keywords
Arc input(s)

$\mathrm{𝚂𝙴𝚃𝚂}$ $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚜𝚎𝚝𝚜},\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝𝚜}\right)$

Arc arity
Arc constraint(s)
 $•\mathrm{𝙸𝙽𝙳𝙴𝚇}=\mathrm{𝚜𝚎𝚝𝚜}.\mathrm{𝚒𝚗𝚍}$ $•$$\mathrm{𝚒𝚗}_\mathrm{𝚜𝚎𝚝}$$\left(\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝𝚜}.\mathrm{𝚔𝚎𝚢},\mathrm{𝚜𝚎𝚝𝚜}.\mathrm{𝚜𝚎𝚝}\right)$
Graph property(ies)
$\mathrm{𝐒𝐔𝐌}$$\left(\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂},\mathrm{𝚌𝚜𝚝}\right)=𝚂$

Graph model

According to the value assigned to $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ the arc constraint selects for the final graph:

• The ${\mathrm{𝙸𝙽𝙳𝙴𝚇}}^{th}$ item of the $\mathrm{𝚂𝙴𝚃𝚂}$ collection,

• The items of the $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$ collection for which the key correspond to the indices of the ${\mathrm{𝙸𝙽𝙳𝙴𝚇}}^{th}$ set of the $\mathrm{𝚂𝙴𝚃𝚂}$ collection.

Finally, since we use the $\mathrm{𝐒𝐔𝐌}$ graph property on the $\mathrm{𝚌𝚜𝚝}$ attribute of the $\mathrm{𝙲𝙾𝙽𝚂𝚃𝙰𝙽𝚃𝚂}$ collection, the last argument $𝚂$ of the $\mathrm{𝚜𝚞𝚖}$ constraint is equal to the sum of the constants associated with the vertices of the final graph.

Parts (A) and (B) of Figure 5.383.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐒𝐔𝐌}$ graph property we show the vertices from which we compute $𝚂$ in a box.