## 5.190. increasing_sum

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi }\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }$.

Arguments
 $\mathrm{\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 }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\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 },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$
Purpose

The variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are increasing. In addition, $\mathrm{\pi }$ is the sum of the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Example
$\left(β©3,3,6,8βͺ,20\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraint holds since:

• The values of the collection $\beta ©3,3,6,8\beta ͺ$ are sorted in increasing order.

• $\mathrm{\pi }=20$ is set to the sum $\beta ©3+3+6+8\beta ͺ$.

Typical
 $|\mathrm{\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 }.\mathrm{\pi \pi \pi }\right)>1$
Arg. properties

Functional dependency: $\mathrm{\pi }$ determined by $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Usage

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraint can be used for breaking some symmetries in bin packing problems. Given a set of $n$ bins with the same maximum capacity, and a set of items each of them with a specific height, the problem is to pack all items in the bins. To break symmetry we order bins by increasing use. This is done by introducing a variable ${x}_{i}$ $\left(0\beta €i for each bin $i$ giving its use, i.e.,Β the sum of items heights assigned to bin $i$, and by posting the following $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\beta ©{x}_{0},{x}_{1},\beta ―,{x}_{n-1}\beta ͺ,s\right)$ where $s$ denotes the sum of the heights of all the items to pack.

Algorithm

A linear time filtering algorithm achieving bound-consistency for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraint is described inΒ [PetitReginBeldiceanu11]. This algorithm was motivated by the fact that achieving bound-consistency on the inequality constraints and on the sum constraint independently hinders propagation, as illustrated by the following small example, where the maximum value of ${x}_{1}$ is not reduced to 2: ${x}_{1}\beta \left[1,3\right]$, ${x}_{2}\beta \left[2,5\right]$, $s\beta \left[5,6\right]$, ${x}_{1}<{x}_{2}$, ${x}_{1}+{x}_{2}=s$.

Given an $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\beta ©{x}_{0},{x}_{1},\beta ―,{x}_{n-1}\beta ͺ,s\right)$ constraint, the bound-consistency algorithm consists of three phases:

1. A normalisation phase adjusts the minimum and maximum value of variables ${x}_{0},{x}_{1},\beta ―,{x}_{n-1}$ with respect to the chain of inequalities ${x}_{0}\beta €{x}_{1}\beta €\beta ―\beta €{x}_{n-1}$. A forward phase adjusts the minimum value of ${x}_{1},{x}_{2},\beta ―,{x}_{n-1}$ (i.e.,Β $\underset{Μ²}{{x}_{i+1}}\beta ₯\underset{Μ²}{{x}_{i}}$), while a backward phase adjusts the maximum value of ${x}_{n-2},{x}_{n-1},\beta ―,{x}_{0}$ (i.e.,Β $\stackrel{Β―}{{x}_{i-1}}\beta €\stackrel{Β―}{{x}_{i}}$).

2. A phase restricts the minimum and maximum value of the sum variable $s$ with respect to the chain of inequalities ${x}_{0}\beta €{x}_{1}\beta €\beta ―\beta €{x}_{n-1}$ (i.e.,Β $\underset{Μ²}{s}\beta ₯{\beta }_{0\beta €i and $\stackrel{Β―}{s}\beta €{\beta }_{0\beta €i).

3. A final phase reduces the minimum and maximum value of variables ${x}_{0},{x}_{1},\beta ―,{x}_{n-1}$ both from the bounds of $s$ and from the chain of inequalities. Without loss of generality we now focus on the pruning of the maximum value of variables ${x}_{0},{x}_{1},\beta ―,{x}_{n-1}$. For this purpose we first need to introduce the notion of last intersecting index of a variable ${x}_{i}$, denoted by . This corresponds to the greatest index in $\left[i+1,n-1\right]$ such that , or $i$ if no such integer exists. Then the increase of the minimum value of $s$ when ${x}_{i}$ is equal to $\stackrel{Β―}{{x}_{i}}$ is equal to . When this increase exceeds the available margin, i.e.Β $\stackrel{Β―}{s}-{\beta }_{0\beta €i, we update the maximum value of ${x}_{i}$.

We illustrate a part of the final phase on the following example $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$$\left(\beta ©{x}_{0},{x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5}\beta ͺ,s\right)$, where ${x}_{0}\beta \left[2,6\right]$, ${x}_{1}\beta \left[4,7\right]$, ${x}_{2}\beta \left[4,7\right]$, ${x}_{3}\beta \left[5,7\right]$, ${x}_{4}\beta \left[6,9\right]$, ${x}_{5}\beta \left[7,9\right]$ and $s\beta \left[28,29\right]$. Observe that the domains are consistent with the first two phases of the algorithm, since,

1. the minimum (and maximum) values of variables ${x}_{0},{x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5}$ are increasing,

2. the sum of the minimum of the variables ${x}_{0},{x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5}$, i.e., 28 is less than or equal to the maximum value of $s$,

3. the sum of the maximum of the variables ${x}_{0},{x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5}$, i.e., 45 is greater than or equal to the minimum value of $s$.

Now, assume we want to know the increase of the minimum value of $s$ when ${x}_{0}$ is set to its maximum value 6. First we compute the last intersecting index of variable ${x}_{0}$. Since ${x}_{4}$ is the last variable for which the minimum value is less than or equal to maximum value of ${x}_{0}$ we have . The increase is equal to ${\beta }_{k\beta \left[0,4\right]}\left(\stackrel{Β―}{{x}_{0}}-\underset{Μ²}{{x}_{k}}\right)=\left(6-2\right)+\left(6-4\right)+\left(6-4\right)+\left(6-5\right)+\left(6-6\right)=9$. Since it exceeds the margin $29-\left(2+4+4+5+6+7\right)=1$ we have to reduce the maximum value of ${x}_{0}$. How to do this incrementally is described inΒ [PetitReginBeldiceanu11].

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 6 20 70 252 924 3432 12870

Number of solutions for $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total62070252924343212870
 Parameter value

01111111
11111111
22222222
31333333
41355555
5-357777
6-379111111
7-2711131515
8-1814182022
9-1716222628
10--718283438
11--519324248
12--520395363
13--320426377
14--219487597
15--1185187116
16--11655100141
17---1455112164
18---1158125194
19---955136221
20---755146255
21---551155284
22---348162319
23---242166348
24---139169383
25---132169409
26----28166440
27----22162461
28----18155486
29----13146499
30----11136515
31----7125519
32----5112526
33----3100519
34----287515
35----175499
36----163486
37-----53461
38-----42440
39-----34409
40-----26383
41-----20348
42-----15319
43-----11284
44-----7255
45-----5221
46-----3194
47-----2164
48-----1141
49-----1116
50------97
51------77
52------63
53------48
54------38
55------28
56------22
57------15
58------11
59------7
60------5
61------3
62------2
63------1
64------1

Solution count for $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$: domains $0..n$

Keywords
Cond. implications

$\beta ’$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi }\right)$

Β Β Β  withΒ  $\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>0$

Β Β implies $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$.

$\beta ’$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi }\right)$

Β Β Β  withΒ  $\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>0$

Β Β implies $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\right)$.