Conjoin $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$ and $\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚌𝚝𝚛}$.

$\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},𝚂)$

$\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚌𝚝𝚛}$, $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚎𝚚}$.

The $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$ constraint holds since:

• The values of the collection $\langle 3,3,6,8\rangle$ are sorted in increasing order.

• $𝚂=20$ is set to the sum $\langle 3+3+6+8\rangle$.

Functional dependency: $𝚂$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

The $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$ constraint can be used for breaking some symmetries in bin packing problems. Given a set of $n$ bins with the same maximum capacity, and a set of items each of them with a specific height, the problem is to pack all items in the bins. To break symmetry we order bins by increasing use. This is done by introducing a variable $x_i$ $(0\le i<n)$ for each bin $i$ giving its use, i.e., the sum of items heights assigned to bin $i$, and by posting the following $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$$(\langle x_0,x_1,\cdots ,x_{n-1}\rangle ,s)$ where $s$ denotes the sum of the heights of all the items to pack.

A linear time filtering algorithm achieving bound-consistency for the $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$ constraint is described in [PetitReginBeldiceanu11]. This algorithm was motivated by the fact that achieving bound-consistency on the inequality constraints and on the sum constraint independently hinders propagation, as illustrated by the following small example, where the maximum value of $x_1$ is not reduced to 2: $x_1\in [1,3]$, $x_2\in [2,5]$, $s\in [5,6]$, $x_1<x_2$, $x_1+x_2=s$.

Given an $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$$(\langle x_0,x_1,\cdots ,x_{n-1}\rangle ,s)$ constraint, the bound-consistency algorithm consists of three phases:

1. A normalisation phase adjusts the minimum and maximum value of variables $x_0,x_1,\cdots ,x_{n-1}$ with respect to the chain of inequalities $x_0\le x_1\le \cdots \le x_{n-1}$. A forward phase adjusts the minimum value of $x_1,x_2,\cdots ,x_{n-1}$ (i.e., $\underline{x_{i+1}}\ge \underline{x_i}$), while a backward phase adjusts the maximum value of $x_{n-2},x_{n-1},\cdots ,x_0$ (i.e., $\overline{x_{i-1}}\le \overline{x_i}$).

2. A phase restricts the minimum and maximum value of the sum variable $s$ with respect to the chain of inequalities $x_0\le x_1\le \cdots \le x_{n-1}$ (i.e., $\underline{s}\ge {\sum }_{0\le i<n}\underline{x_i}$ and $\overline{s}\le {\sum }_{0\le i<n}\overline{x_i}$).

3. A final phase reduces the minimum and maximum value of variables $x_0,x_1,\cdots ,x_{n-1}$ both from the bounds of $s$ and from the chain of inequalities. Without loss of generality we now focus on the pruning of the maximum value of variables $x_0,x_1,\cdots ,x_{n-1}$. For this purpose we first need to introduce the notion of last intersecting index of a variable $x_i$, denoted by ${\mathrm{𝑙𝑎𝑠𝑡}}_i$. This corresponds to the greatest index in $[i+1,n-1]$ such that $\overline{x_i}>\underline{x_{{\mathrm{𝑙𝑎𝑠𝑡}}_i}}$, or $i$ if no such integer exists. Then the increase of the minimum value of $s$ when $x_i$ is equal to $\overline{x_i}$ is equal to ${\sum }_{k\in [i,{\mathrm{𝑙𝑎𝑠𝑡}}_i]}(\overline{x_i}-\underline{x_k})$. When this increase exceeds the available margin, i.e. $\overline{s}-{\sum }_{0\le i<n}\underline{x_i}$, we update the maximum value of $x_i$.

We illustrate a part of the final phase on the following example $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$$(\langle x_0,x_1,x_2,x_3,x_4,x_5\rangle ,s)$, where $x_0\in [2,6]$, $x_1\in [4,7]$, $x_2\in [4,7]$, $x_3\in [5,7]$, $x_4\in [6,9]$, $x_5\in [7,9]$ and $s\in [28,29]$. Observe that the domains are consistent with the first two phases of the algorithm, since,

1. the minimum (and maximum) values of variables $x_0,x_1,x_2,x_3,x_4,x_5$ are increasing,

2. the sum of the minimum of the variables $x_0,x_1,x_2,x_3,x_4,x_5$, i.e., 28 is less than or equal to the maximum value of $s$,

3. the sum of the maximum of the variables $x_0,x_1,x_2,x_3,x_4,x_5$, i.e., 45 is greater than or equal to the minimum value of $s$.

Now, assume we want to know the increase of the minimum value of $s$ when $x_0$ is set to its maximum value 6. First we compute the last intersecting index of variable $x_0$. Since $x_4$ is the last variable for which the minimum value is less than or equal to maximum value of $x_0$ we have ${\mathrm{𝑙𝑎𝑠𝑡}}_0=4$. The increase is equal to ${\sum }_{k\in [0,4]}(\overline{x_0}-\underline{x_k})=(6-2)+(6-4)+(6-4)+(6-5)+(6-6)=9$. Since it exceeds the margin $29-(2+4+4+5+6+7)=1$ we have to reduce the maximum value of $x_0$. How to do this incrementally is described in [PetitReginBeldiceanu11].

Number of solutions for $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$: domains $0..n$

Solution count for $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚜𝚞𝚖}$: domains $0..n$

common keyword: $\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚌𝚝𝚛}$ (sum).

implies: $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$.

characteristic of a constraint: sum.

constraint type: predefined constraint, order constraint, arithmetic constraint.

filtering: bound-consistency.

modelling: functional dependency.

symmetry: symmetry.