## 5.342. scalar_product

Origin

Arithmetic constraint.

Constraint

$\mathrm{𝚜𝚌𝚊𝚕𝚊𝚛}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼},\mathrm{𝙲𝚃𝚁},\mathrm{𝚅𝙰𝙻}\right)$

Synonyms

$\mathrm{𝚎𝚚𝚞𝚊𝚝𝚒𝚘𝚗}$, $\mathrm{𝚕𝚒𝚗𝚎𝚊𝚛}$, $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝}$, $\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝𝚎𝚍𝚂𝚞𝚖}$.

Arguments
 $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚌𝚘𝚎𝚏𝚏}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙲𝚃𝚁}$ $\mathrm{𝚊𝚝𝚘𝚖}$ $\mathrm{𝚅𝙰𝙻}$ $\mathrm{𝚍𝚟𝚊𝚛}$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼},\left[\mathrm{𝚌𝚘𝚎𝚏𝚏},\mathrm{𝚟𝚊𝚛}\right]\right)$ $\mathrm{𝙲𝚃𝚁}\in \left[=,\ne ,<,\ge ,>,\le \right]$
Purpose

Constraint a linear term defined as the sum of products of coefficients and variables. More precisely, let $𝚂$ denote the sum of the product between a coefficient and its variable of the different items of the $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}$ collection. Enforce the following constraint to hold: $𝚂\mathrm{𝙲𝚃𝚁}\mathrm{𝚅𝙰𝙻}$.

Example
$\left(\begin{array}{c}〈\mathrm{𝚌𝚘𝚎𝚏𝚏}-1\mathrm{𝚟𝚊𝚛}-1,\mathrm{𝚌𝚘𝚎𝚏𝚏}-3\mathrm{𝚟𝚊𝚛}-1,\mathrm{𝚌𝚘𝚎𝚏𝚏}-1\mathrm{𝚟𝚊𝚛}-4〉,=,8\hfill \end{array}\right)$

The $\mathrm{𝚜𝚌𝚊𝚕𝚊𝚛}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint holds since the condition $1·1+3·1+1·4=8$ is satisfied.

Typical
 $|\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}.\mathrm{𝚌𝚘𝚎𝚏𝚏}\right)>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}.\mathrm{𝚟𝚊𝚛}\right)>1$ $\mathrm{𝙲𝚃𝚁}\in \left[=,<,\ge ,>,\le \right]$
Symmetries
• Items of $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}$ are permutable.

• Attributes of $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}$ are permutable w.r.t. permutation $\left(\mathrm{𝚌𝚘𝚎𝚏𝚏},\mathrm{𝚟𝚊𝚛}\right)$ (permutation not necessarily applied to all items).

Arg. properties
• Contractible wrt. $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}$ when $\mathrm{𝙲𝚃𝚁}\in \left[<,\le \right]$, $\mathrm{𝚖𝚒𝚗𝚟𝚊𝚕}\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}.\mathrm{𝚌𝚘𝚎𝚏𝚏}\right)\ge 0$ and $\mathrm{𝚖𝚒𝚗𝚟𝚊𝚕}\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}.\mathrm{𝚟𝚊𝚛}\right)\ge 0$.

• Extensible wrt. $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}$ when $\mathrm{𝙲𝚃𝚁}\in \left[\ge ,>\right]$, $\mathrm{𝚖𝚒𝚗𝚟𝚊𝚕}\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}.\mathrm{𝚌𝚘𝚎𝚏𝚏}\right)\ge 0$ and $\mathrm{𝚖𝚒𝚗𝚟𝚊𝚕}\left(\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}.\mathrm{𝚟𝚊𝚛}\right)\ge 0$.

• Aggregate: $\mathrm{𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼}\left(\mathrm{𝚞𝚗𝚒𝚘𝚗}\right)$, $\mathrm{𝙲𝚃𝚁}\left(\mathrm{𝚒𝚍}\right)$, $\mathrm{𝚅𝙰𝙻}\left(+\right)$.

Remark

The $\mathrm{𝚜𝚌𝚊𝚕𝚊𝚛}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint is called $\mathrm{𝚕𝚒𝚗𝚎𝚊𝚛}$ in Gecode (http://www.gecode.org/). It is called $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝}$ in JaCoP (http://www.jacop.eu/). In the 2008 CSP solver competition the $\mathrm{𝚜𝚌𝚊𝚕𝚊𝚛}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint was called $\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝𝚎𝚍𝚂𝚞𝚖}$ and required $\mathrm{𝚅𝙰𝙻}$ to be fixed.

Algorithm

Most filtering algorithms first merge multiple occurrences of identical variables in order to potentially make more deductions. When $\mathrm{𝙲𝚃𝚁}$ corresponds to the less than or equal to constraint, a filtering algorithm achieving bound-consistency for the $\mathrm{𝚜𝚌𝚊𝚕𝚊𝚛}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint with large numbers of variables is described in [HarveySchimpf02].

Systems
specialisation: $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$ (arithmetic constraint where all coefficients are equal to 1).