5.286. scalar_product

DESCRIPTIONLINKS
Origin

Arithmetic constraint.

Constraint

πšœπšŒπšŠπš•πšŠπš›_πš™πš›πš˜πšπšžπšŒπš(π™»π™Έπ™½π™΄π™°πšπšƒπ™΄πšπ™Ό,π™²πšƒπš,πš…π™°π™»)

Synonyms

πšŽπššπšžπšŠπšπš’πš˜πš—, πš•πš’πš—πšŽπšŠπš›, πšœπšžπš–_πš πšŽπš’πšπš‘πš, πš πšŽπš’πšπš‘πšπšŽπšπš‚πšžπš–.

Arguments
π™»π™Έπ™½π™΄π™°πšπšƒπ™΄πšπ™ΌπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚌𝚘𝚎𝚏𝚏-πš’πš—πš,πšŸπšŠπš›-πšπšŸπšŠπš›)
π™²πšƒπšπšŠπšπš˜πš–
πš…π™°π™»πšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™»π™Έπ™½π™΄π™°πšπšƒπ™΄πšπ™Ό,[𝚌𝚘𝚎𝚏𝚏,πšŸπšŠπš›])
π™²πšƒπšβˆˆ[=,β‰ ,<,β‰₯,>,≀]
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 π™»π™Έπ™½π™΄π™°πšπšƒπ™΄πšπ™Ό collection. Enforce the following constraint to hold: πš‚ π™²πšƒπš πš…π™°π™».

Example
𝚌𝚘𝚎𝚏𝚏-1πšŸπšŠπš›-1,𝚌𝚘𝚎𝚏𝚏-3πšŸπšŠπš›-1,𝚌𝚘𝚎𝚏𝚏-1πšŸπšŠπš›-4,=,8

The πšœπšŒπšŠπš•πšŠπš›_πš™πš›πš˜πšπšžπšŒπš constraint holds since the condition 1Β·1+3Β·1+1Β·4=8 is satisfied.

Symmetries
  • Items of π™»π™Έπ™½π™΄π™°πšπšƒπ™΄πšπ™Ό are permutable.

  • Attributes of π™»π™Έπ™½π™΄π™°πšπšƒπ™΄πšπ™Ό are permutable w.r.t. permutation (𝚌𝚘𝚎𝚏𝚏,πšŸπšŠπš›) (permutation not necessarily applied to all items).

Remark

The πšœπšŒπšŠπš•πšŠπš›_πš™πš›πš˜πšπšžπšŒπš constraint is called πš•πš’πš—πšŽπšŠπš› in Gecode (http://www.gecode.org/). It is called πšœπšžπš–_πš πšŽπš’πšπš‘πš in JaCoP (http://www.jacop.eu/). In the 2008 CSP solver competition the πšœπšŒπšŠπš•πšŠπš›_πš™πš›πš˜πšπšžπšŒπš constraint was called πš πšŽπš’πšπš‘πšπšŽπšπš‚πšžπš– and required πš…π™°π™» to be fixed.

Algorithm

Most filtering algorithms first merge multiple occurrences of identical variables in order to potentially make more deductions. When π™²πšƒπš corresponds to the less than or equal to constraint, a filtering algorithm achieving bound-consistency for the πšœπšŒπšŠπš•πšŠπš›_πš™πš›πš˜πšπšžπšŒπš constraint with large numbers of variables is described inΒ [HarveySchimpf02].

Systems

equation in Choco, sumweight in JaCoP, scalar_product in SICStus.

See also

specialisation: πšœπšžπš–_πšŒπšπš›Β (arithmetic constraint where all coefficients are equal to 1).

Keywords

characteristic of a constraint: sum.

constraint type: predefined constraint, arithmetic constraint.

filtering: duplicated variables.