## 5.210. maximum

 DESCRIPTION LINKS GRAPH AUTOMATON
Origin

CHIP

Constraint

$\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}\left(\mathrm{𝙼𝙰𝚇},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Synonym

$\mathrm{𝚖𝚊𝚡}$.

Arguments
 $\mathrm{𝙼𝙰𝚇}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

$\mathrm{𝙼𝙰𝚇}$ is the maximum value of the collection of domain variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Example
$\left(7,〈3,2,7,2,6〉\right)$

The $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint holds since its first argument $\mathrm{𝙼𝙰𝚇}=7$ is fixed to the maximum value of the collection $〈3,2,7,2,6〉$.

Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• All occurrences of two distinct values of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be swapped.

• One and the same constant can be added to $\mathrm{𝙼𝙰𝚇}$ as well as to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

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{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint to get the maximum completion time of a set of tasks.

Remark

Note that $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ is a constraint and not just a function that computes the maximum value of a collection of variables: potential values of $\mathrm{𝙼𝙰𝚇}$ influence the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, and reciprocally potential values that can be assigned to variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ influence $\mathrm{𝙼𝙰𝚇}$.

The $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint is called $\mathrm{𝚖𝚊𝚡}$ in JaCoP (http://www.jacop.eu/).

Algorithm
Systems

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

See also

generalisation: $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}_\mathrm{𝚖𝚘𝚍𝚞𝚕𝚘}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\mathrm{mod}\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$).

specialisation: $\mathrm{𝚖𝚊𝚡}_𝚗$ (maximum or order $𝚗$ replaced by absolute maximum).

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\bigvee \left(\begin{array}{c}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚔𝚎𝚢}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚔𝚎𝚢},\hfill \\ \mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}>\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\hfill \end{array}\right)$
Graph property(ies)
$\mathrm{𝐎𝐑𝐃𝐄𝐑}$$\left(0,\mathrm{𝙼𝙸𝙽𝙸𝙽𝚃},\mathrm{𝚟𝚊𝚛}\right)=\mathrm{𝙼𝙰𝚇}$

Graph model

We use a similar definition that the one that was utilised for the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ 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{𝐎𝐑𝐃𝐄𝐑}$ graph property, the vertex of rank 0 (without considering the loops) of the final graph is outlined with a thick circle.

##### Figure 5.210.1. Initial and final graph of the $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint  (a) (b)
Automaton

Figure 5.210.2 depicts the automaton associated with the $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint. Let ${\mathrm{𝚅𝙰𝚁}}_{i}$ be the ${i}^{th}$ variable of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. To each pair $\left(\mathrm{𝙼𝙰𝚇},{\mathrm{𝚅𝙰𝚁}}_{i}\right)$ corresponds a signature variable ${𝚂}_{i}$ as well as the following signature constraint: $\left(\mathrm{𝙼𝙰𝚇}>{\mathrm{𝚅𝙰𝚁}}_{i}⇔{𝚂}_{i}=0\right)\wedge \left(\mathrm{𝙼𝙰𝚇}={\mathrm{𝚅𝙰𝚁}}_{i}⇔{𝚂}_{i}=1\right)\wedge \left(\mathrm{𝙼𝙰𝚇}<{\mathrm{𝚅𝙰𝚁}}_{i}⇔{𝚂}_{i}=2\right)$.

##### Figure 5.210.2. Automaton of the $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint ##### Figure 5.210.3. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint 