Global Constraint Catalog: Cmaximum

5.249. 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〉)

(1, 〈0, 0, 1, 0, 1〉)

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

Typical

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

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

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 $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Arg. properties

Functional dependency: $𝙼𝙰𝚇$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Aggregate: $𝙼𝙰𝚇 (𝚖𝚊𝚡)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ .

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

A filtering algorithm for the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint is described in [Beldiceanu01].

The $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint is entailed if all the following conditions hold:

$𝙼𝙰𝚇$ is fixed.
At least one variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ is assigned value $𝙼𝙰𝚇$ .
All variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ have their maximum value less than or equal to value $𝙼𝙰𝚇$ .

Counting

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

Number of solutions for $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ : domains $0 . . n$

ctrs/maximum-1-tikz

ctrs/maximum-2-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

127

255

211

665

2059

6305

175

781

3367

14197

58975

369

2101

11529

61741

325089

4651

31031

201811

1288991

70993

543607

4085185

1273609

11012415

26269505

Solution count for $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ : domains $0 . . n$

ctrs/maximum-3-tikz

ctrs/maximum-4-tikz

Systems

max in Choco, max in Gecode, max in JaCoP, maximum in MiniZinc, 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 arguments: reverse of a constraint, pure functional dependency.

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

constraint type: order constraint.

filtering: glue matrix, arc-consistency, entailment.

modelling: balanced assignment, functional dependency.

Cond. implications

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

with $𝚏𝚒𝚛𝚜𝚝 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) < 𝙼𝙰𝚇$

and $𝚕𝚊𝚜𝚝 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) < 𝙼𝙰𝚇$

implies $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ $(𝙷𝙴𝙸𝙶𝙷𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

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.249.1 respectively show the initial and final graph associated with the first example of 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.249.1. Initial and final graph of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint


(a)	(b)

Automaton

Figure 5.249.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 $S_{i}$ as well as the following signature constraint: $(𝙼𝙰𝚇 > {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 0) \land (𝙼𝙰𝚇 = {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 1) \land (𝙼𝙰𝚇 < {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 2)$ .

Figure 5.249.2. Counter free automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

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

Figure 5.249.3 depicts a second counter free non deterministic automaton associated with the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint, where the argument $𝙼𝙰𝚇$ is also part of the sequence passed to the automaton.

Figure 5.249.4. Counter free non deterministic automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ $(𝙼𝙰𝚇, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint assuming that the union of the domain of the variables is the set ${1, 2, 3, 4}$ and that the elements of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are first passed to the automaton followed by $𝙼𝙰𝚇$ (state $s_{i}$ means that no value strictly greater than value $i$ was found and that value $i$ was already encountered at least once)

Figure 5.249.5. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.249.6 depicts a third deterministic automaton with one counter associated with the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint, where the argument $𝙼𝙰𝚇$ is unified to the final value of the counter.

Figure 5.249.6. Automaton (with one counter) of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint and its glue constraint

Figure 5.249.7. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint: since all states variables $Q_{0}, Q_{1}, \dots, Q_{n}$ are fixed to the unique state $s$ of the automaton, the transitions constraints share only the counter variable $C$ and the constraint network is Berge-acyclic

Global Constraint Catalog

5. Global Constraint Catalogue

5.249. maximum

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

Figure 5.249.2. Counter free automaton of the 𝚖𝚊𝚡𝚒𝚖𝚞𝚖 constraint

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

Figure 5.249.5. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the 𝚖𝚊𝚡𝚒𝚖𝚞𝚖 constraint

Figure 5.249.6. Automaton (with one counter) of the 𝚖𝚊𝚡𝚒𝚖𝚞𝚖 constraint and its glue constraint

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

Figure 5.249.2. Counter free automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

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

Figure 5.249.5. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint

Figure 5.249.6. Automaton (with one counter) of the $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ constraint and its glue constraint