Global Constraint Catalog: Cmaximum

5.210. maximum

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

$𝚖𝚊𝚡𝚒𝚖𝚞𝚖 (𝙼𝙰𝚇, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonym

$𝚖𝚊𝚡$ .

Arguments

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

Restrictions

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

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

Example

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

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

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
All occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped.
One and the same constant can be added to $𝙼𝙰𝚇$ as well as to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

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

Remark

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

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

Algorithm

[Beldiceanu01].

Systems

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

comparison swapped: $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ .

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

implied by: $𝚘𝚛$ .

implies: $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ , $𝚒𝚗$ .

soft variant: $𝚘𝚙𝚎𝚗_𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ (open constraint).

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

uses in its reformulation: $𝚝𝚛𝚎𝚎_𝚛𝚊𝚗𝚐𝚎$ .

Keywords

characteristic of a constraint: maximum, automaton, automaton without counters, reified automaton constraint.

constraint network structure: centered cyclic(1) constraint network(1).

constraint type: order constraint.

filtering: arc-consistency.

modelling: balanced assignment.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

⋁ (\begin{matrix} 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚔𝚎𝚢 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚔𝚎𝚢, \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 > 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 \end{matrix})

Graph property(ies)

𝐎𝐑𝐃𝐄𝐑

(0, 𝙼𝙸𝙽𝙸𝙽𝚃, 𝚟𝚊𝚛) = 𝙼𝙰𝚇

Graph model

We use a similar definition that the one that was utilised for the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ 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 $𝐎𝐑𝐃𝐄𝐑$ 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 $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint


(a)	(b)

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

Figure 5.210.2. Automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.210.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.210. maximum

Figure 5.210.1. Initial and final graph of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.210.2. Automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.210.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.210. maximum

Figure 5.210.1. Initial and final graph of the 𝚖𝚊𝚡𝚒𝚖𝚞𝚖 constraint

Figure 5.210.2. Automaton of the 𝚖𝚊𝚡𝚒𝚖𝚞𝚖 constraint

Figure 5.210.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚖𝚊𝚡𝚒𝚖𝚞𝚖 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.210.1. Initial and final graph of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.210.2. Automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.210.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint