## 5.249. maximum

Origin

CHIP

Constraint

$\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi °\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonym

$\mathrm{\pi \pi \pi ‘}$.

Arguments
 $\mathrm{\pi Ό\pi °\pi }$ $\mathrm{\pi \pi \pi \pi }$ $\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)$
Restrictions
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>0$ $\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)$
Purpose

$\mathrm{\pi Ό\pi °\pi }$ is the maximum value of the collection of domain variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Example
 $\left(7,β©3,2,7,2,6βͺ\right)$ $\left(1,β©0,0,1,0,1βͺ\right)$

The first $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint holds since its first argument $\mathrm{\pi Ό\pi °\pi }=7$ is fixed to the maximum value of the collection $\beta ©3,2,7,2,6\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$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• All occurrences of two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be swapped.

• One and the same constant can be added to $\mathrm{\pi Ό\pi °\pi }$ as well as to the $\mathrm{\pi \pi \pi }$ attribute of all items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

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

• Aggregate: $\mathrm{\pi Ό\pi °\pi }\left(\mathrm{\pi \pi \pi ‘}\right)$, $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left(\mathrm{\pi \pi \pi \pi \pi }\right)$.

Usage

In some project scheduling problems one has to introduce dummy activities that correspond for instance to the completion time of a given set of activities. In this context one can use the $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint to get the maximum completion time of a set of tasks.

Remark

Note that $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ is a constraint and not just a function that computes the maximum value of a collection of variables: potential values of $\mathrm{\pi Ό\pi °\pi }$ influence the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$, and reciprocally potential values that can be assigned to variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ influence $\mathrm{\pi Ό\pi °\pi }$.

The $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint is called $\mathrm{\pi \pi \pi ‘}$ in JaCoP (http://www.jacop.eu/).

Algorithm

A filtering algorithm for the $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint is described inΒ [Beldiceanu01].

The $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint is entailed if all the following conditions hold:

1. $\mathrm{\pi Ό\pi °\pi }$ is fixed.

2. At least one variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ is assigned value $\mathrm{\pi Ό\pi °\pi }$.

3. All variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ have their maximum value less than or equal to value $\mathrm{\pi Ό\pi °\pi }$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

01111111
137153163127255
25196521166520596305
3-3717578133671419758975
4--36921011152961741325089
5---4651310312018111288991
6----709935436074085185
7-----127360911012415
8------26269505

Solution count for $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$: domains $0..n$

Systems

max in Choco, max in Gecode, max in JaCoP, maximum in MiniZinc, maximum in SICStus.

generalisation: $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\mathrm{mod}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$).

specialisation: $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi }$Β (maximum or order $\mathrm{\pi }$ replaced by absolute maximum).

Keywords
Cond. implications

$\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi °\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Β Β Β  withΒ  $\mathrm{\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 }$

Β Β Β  andΒ Β  $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)<\mathrm{\pi Ό\pi °\pi }$

Β Β implies $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi ·\pi ΄\pi Έ\pi Ά\pi ·\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$.

Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\beta \left(\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi ’}=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi ’},\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }>\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }\hfill \end{array}\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi \pi }$$\left(0,\mathrm{\pi Ό\pi Έ\pi ½\pi Έ\pi ½\pi },\mathrm{\pi \pi \pi }\right)=\mathrm{\pi Ό\pi °\pi }$

Graph model

We use a similar definition that the one that was utilised for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint. Within the arc constraint, we replace the comparison operator $<$ by $>$.

PartsΒ (A) andΒ (B) of FigureΒ 5.249.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi \pi }$ graph property, the vertex of rank 0 (without considering the loops) of the final graph is outlined with a thick circle.

Automaton

FigureΒ 5.249.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint. Let ${\mathrm{\pi  \pi °\pi }}_{i}$ be the ${i}^{th}$ variable of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. To each pair $\left(\mathrm{\pi Ό\pi °\pi },{\mathrm{\pi  \pi °\pi }}_{i}\right)$ corresponds a signature variable ${S}_{i}$ as well as the following signature constraint: $\left(\mathrm{\pi Ό\pi °\pi }>{\mathrm{\pi  \pi °\pi }}_{i}\beta {S}_{i}=0\right)\beta §\left(\mathrm{\pi Ό\pi °\pi }={\mathrm{\pi  \pi °\pi }}_{i}\beta {S}_{i}=1\right)\beta §\left(\mathrm{\pi Ό\pi °\pi }<{\mathrm{\pi  \pi °\pi }}_{i}\beta {S}_{i}=2\right)$.

FigureΒ 5.249.3 depicts a second counter free non deterministic automaton associated with the $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint, where the argument $\mathrm{\pi Ό\pi °\pi }$ is also part of the sequence passed to the automaton.

FigureΒ 5.249.6 depicts a third deterministic automaton with one counter associated with the $\mathrm{\pi \pi \pi ‘\pi \pi \pi \pi }$ constraint, where the argument $\mathrm{\pi Ό\pi °\pi }$ is unified to the final value of the counter.