Link Search Menu Expand Document
Specifications PyCSP3 Tools Instances Competitions About

Constraint sum

The constraint sum is one of the most important constraint. When the optional element coeffs is missing, it is assumed that all coefficients are equal to 1. The constraint is subject to a numerical condition $(\odot,k)$ composed of an operator in {lt,le,ge,gt,eq,ne,in,notin} and a right operand which is an integer value, a variable, an integer interval or a set of integers.

sum($X$,$C$,($\odot$,$k$)) with $X=\langle x_1,x_2,\ldots \rangle$ and $C=\langle c_1,c_2,\ldots\rangle$, iff $(\sum_{i = 1}^{|X|} c_i \times x_i) \odot k$.

Syntax

<sum>
   <list> (intVar wspace)2+ </list>
   [ <coeffs> (intVal wspace)2+ | (intVar wspace)2+ </coeffs> ] 
   <condition> "(" operator "," operand ")" </condition> 
</sum>

The following constraint states that the values taken by variables x1 ,x2, x3 and y must respect the linear function x1 * 1 + x2 * 2 + x3* 3 $\gt$ y.

Example

<sum>
  <list> x1 x2 x3 </list>
  <coeffs> 1 2 3 </coeffs>
  <condition> (gt,y) </condition>  
</sum>

A form of sum, sometimes called subset-sum or knapsack, see [T03] and [PQ08], involves the operator ``in’’, and ensures that the obtained sum belongs (or not) to a specified interval. The following constraint states that the values taken by variables y1,y2,y3,y4 must respect 2 $\leq$ y1 * 4 + y2 * 2 + y3 * 3 + y4 * 1 $\leq$ 5.

Example

<sum>
  <list> y1 y2 y3 y4 </list>
  <coeffs> 4 2 3 1 </coeffs>
  <condition> (in,2..5) </condition>  
</sum>