## 5.210. 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)$

The $\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 ͺ$.

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 }$.

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
Systems

max in Choco, max in Gecode, max in JaCoP, 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
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.210.1 respectively show the initial and final graph associated with 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.210.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 ${\mathrm{\pi }}_{i}$ as well as the following signature constraint: $\left(\mathrm{\pi Ό\pi °\pi }>{\mathrm{\pi  \pi °\pi }}_{i}\beta {\mathrm{\pi }}_{i}=0\right)\beta §\left(\mathrm{\pi Ό\pi °\pi }={\mathrm{\pi  \pi °\pi }}_{i}\beta {\mathrm{\pi }}_{i}=1\right)\beta §\left(\mathrm{\pi Ό\pi °\pi }<{\mathrm{\pi  \pi °\pi }}_{i}\beta {\mathrm{\pi }}_{i}=2\right)$.