Global Constraint Catalog: Csum_of

5.387. sum_of_increments

DESCRIPTION

LINKS

Origin

[Brand09]

Constraint

$𝚜𝚞𝚖_𝚘𝚏_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙻𝙸𝙼𝙸𝚃)$

Synonyms

$𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜_𝚜𝚞𝚖$ , $𝚒𝚗𝚌𝚛_𝚜𝚞𝚖$ , $𝚜𝚞𝚖_𝚒𝚗𝚌𝚛$ , $𝚜𝚞𝚖_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜$ .

Arguments

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙻𝙸𝙼𝙸𝚃$	$𝚍𝚟𝚊𝚛$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \geq 0

𝙻𝙸𝙼𝙸𝚃 \geq 0

Purpose

Given a collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ which can only be assigned non negative values, and a variable $𝙻𝙸𝙼𝙸𝚃$ , enforce the condition $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [1] . 𝚟𝚊𝚛 + \sum_{i = 2}^{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |} max (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚟𝚊𝚛 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i - 1] . 𝚟𝚊𝚛, 0) \leq 𝙻𝙸𝙼𝙸𝚃$ . $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [1] . 𝚟𝚊𝚛$ stands from the fact that we assume an additional implicit 0 before the first variable (i.e., $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [1] . 𝚟𝚊𝚛 = max (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [1] . 𝚟𝚊𝚛 - 0, 0)$ ).

Example

(〈4, 4, 3, 4, 6〉, 7)

The $𝚜𝚞𝚖_𝚘𝚏_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜$ constraint holds since we have that $4 + max (4 - 4, 0) + max (3 - 4, 0) + max (4 - 3, 0) + max (6 - 4, 0) \leq 7$ .

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 2

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

𝚖𝚊𝚡𝚟𝚊𝚕

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 0

𝙻𝙸𝙼𝙸𝚃 > 0

𝙻𝙸𝙼𝙸𝚃 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | *

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) / 2

Symmetries

One and the same constant can be added to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ and to $𝙻𝙸𝙼𝙸𝚃$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
$𝙻𝙸𝙼𝙸𝚃$ can be increased.

Arg. properties

Prefix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Suffix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Usage

The $𝚜𝚞𝚖_𝚘𝚏_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜$ was initially motivated by the problem of decomposing a matrix of non-negative integers into a positive linear combination of matrices consisting of only zeros and ones, where the ones occur consecutively in each row.

Algorithm

A $O (| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)$ bound-consistency filtering algorithm for the $𝚜𝚞𝚖_𝚘𝚏_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜$ constraint is described in [Brand09].

Reformulation

The following reformulations are provided in [Brand09]. Assuming $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [0] . 𝚟𝚊𝚛$ is defined as 0 (i.e., a zero is added before the first variable of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection) we have:

$\sum_{i = 1}^{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |} S_{i} \leq 𝙻𝙸𝙼𝙸𝚃$ with $D_{i} = 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚟𝚊𝚛 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i - 1] . 𝚟𝚊𝚛$ and $S_{i} = max (D_{i}, 0)$ $(1 \leq i \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)$ .
$\sum_{i = 1}^{| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |} S_{i} \leq 𝙻𝙸𝙼𝙸𝚃$ with $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚟𝚊𝚛 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i - 1] . 𝚟𝚊𝚛 \leq S_{i}$ and $S_{i} \in [0, \bar{𝙻𝙸𝙼𝙸𝚃}]$ $(1 \leq i \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	14	145	2875	51415	1210104	28573741	801944469

Number of solutions for $𝚜𝚞𝚖_𝚘𝚏_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜$ : domains $0 . . n$

ctrs/sum_of_increments-1-tikz

ctrs/sum_of_increments-2-tikz

Length (

n

)

Total

145

2875

51415

1210104

28573741

801944469

Parameter

value

101

183

309

493

156

396

904

1891

3679

375

1167

3235

8135

18835

485

2848

9318

27483

74143

563

4263

22981

77947

240751

608

5568

38836

193742

675244

625

6616

56703

359880

1688427

7314

74658

578511

3369015

7650

90639

837441

5865915

7720

102875

1115687

9220695

7755

110425

1386029

13354545

113827

1619993

18051195

115857

1795694

22965651

116942

1908968

27670800

117437

1988222

31755573

117612

2039616

34989993

117649

2069933

37574073

2085763

39526569

2092817

40912205

2095436

41827847

2096360

42386387

2096822

42700112

2097032

42865683

42953199

43002171

43027581

43039551

43044507

43046215

43046656

43046721

Solution count for $𝚜𝚞𝚖_𝚘𝚏_𝚒𝚗𝚌𝚛𝚎𝚖𝚎𝚗𝚝𝚜$ : domains $0 . . n$

ctrs/sum_of_increments-3-tikz

ctrs/sum_of_increments-4-tikz

Keywords

characteristic of a constraint: difference, sum.

constraint type: predefined constraint.

filtering: bound-consistency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.387. sum_of_increments