## 5.342. scalar_product

Origin

Arithmetic constraint.

Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό},\mathrm{\pi ²\pi \pi },\mathrm{\pi  \pi °\pi »}\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi }$, , .

Arguments
 $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi ²\pi \pi }$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi »}$ $\mathrm{\pi \pi \pi \pi }$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό},\left[\mathrm{\pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi }\right]\right)$
Purpose

Constraint a linear term defined as the sum of products of coefficients and variables. More precisely, let $\mathrm{\pi }$ denote the sum of the product between a coefficient and its variable of the different items of the $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}$ collection. Enforce the following constraint to hold: $\mathrm{\pi }\mathrm{\pi ²\pi \pi }\mathrm{\pi  \pi °\pi »}$.

Example
$\left(\begin{array}{c}β©\mathrm{\pi \pi \pi \pi \pi }-1\mathrm{\pi \pi \pi }-1,\mathrm{\pi \pi \pi \pi \pi }-3\mathrm{\pi \pi \pi }-1,\mathrm{\pi \pi \pi \pi \pi }-1\mathrm{\pi \pi \pi }-4βͺ,=,8\hfill \end{array}\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint holds since the condition $1Β·1+3Β·1+1Β·4=8$ is satisfied.

Typical
 $|\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}.\mathrm{\pi \pi \pi \pi \pi }\right)>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}.\mathrm{\pi \pi \pi }\right)>1$ $\mathrm{\pi ²\pi \pi }\beta \left[=,<,\beta ₯,>,\beta €\right]$
Symmetries
• Items of $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}$ are permutable.

• Attributes of $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}$ are permutable w.r.t. permutation $\left(\mathrm{\pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi }\right)$ (permutation not necessarily applied to all items).

Arg. properties
• Contractible wrt. $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}$ when $\mathrm{\pi ²\pi \pi }\beta \left[<,\beta €\right]$, $\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}.\mathrm{\pi \pi \pi \pi \pi }\right)\beta ₯0$ and $\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}.\mathrm{\pi \pi \pi }\right)\beta ₯0$.

• Extensible wrt. $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}$ when $\mathrm{\pi ²\pi \pi }\beta \left[\beta ₯,>\right]$, $\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}.\mathrm{\pi \pi \pi \pi \pi }\right)\beta ₯0$ and $\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}.\mathrm{\pi \pi \pi }\right)\beta ₯0$.

• Aggregate: $\mathrm{\pi »\pi Έ\pi ½\pi ΄\pi °\pi \pi \pi ΄\pi \pi Ό}\left(\mathrm{\pi \pi \pi \pi \pi }\right)$, $\mathrm{\pi ²\pi \pi }\left(\mathrm{\pi \pi }\right)$, $\mathrm{\pi  \pi °\pi »}\left(+\right)$.

Remark

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint is called $\mathrm{\pi \pi \pi \pi \pi \pi }$ in Gecode (http://www.gecode.org/). It is called in JaCoP (http://www.jacop.eu/). In the 2008 CSP solver competition the $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint was called and required $\mathrm{\pi  \pi °\pi »}$ to be fixed.

Algorithm

Most filtering algorithms first merge multiple occurrences of identical variables in order to potentially make more deductions. When $\mathrm{\pi ²\pi \pi }$ corresponds to the less than or equal to constraint, a filtering algorithm achieving bound-consistency for the $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint with large numbers of variables is described inΒ [HarveySchimpf02].

Systems
specialisation: $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$Β (arithmetic constraint where all coefficients are equal to 1).