5.210. maximum

DESCRIPTIONLINKSGRAPHAUTOMATON
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.

See also

common keyword: πš–πš’πš—πš’πš–πšžπš–Β (order constraint).

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
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β‹πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›>πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
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
ctrs/maximumActrs/maximumB
(a) (b)
Automaton

FigureΒ 5.210.2 depicts the automaton associated with the πš–πšŠπš‘πš’πš–πšžπš– constraint. Let πš…π™°πš i be the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. To each pair (π™Όπ™°πš‡,πš…π™°πš i ) corresponds a signature variable πš‚ i as well as the following signature constraint: (π™Όπ™°πš‡>πš…π™°πš i β‡”πš‚ i =0) ∧(π™Όπ™°πš‡=πš…π™°πš i β‡”πš‚ i =1) ∧(π™Όπ™°πš‡<πš…π™°πš i β‡”πš‚ i =2).

Figure 5.210.2. Automaton of the πš–πšŠπš‘πš’πš–πšžπš– constraint
ctrs/maximum1
Figure 5.210.3. Hypergraph of the reformulation corresponding to the automaton of the πš–πšŠπš‘πš’πš–πšžπš– constraint
ctrs/maximum2