5.217. minimum

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

πš–πš’πš—πš’πš–πšžπš–(𝙼𝙸𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonym

πš–πš’πš—.

Arguments
π™Όπ™Έπ™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

𝙼𝙸𝙽 is the minimum value of the collection of domain variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(2,3,2,7,2,6)

The πš–πš’πš—πš’πš–πšžπš– constraint holds since its first argument 𝙼𝙸𝙽=2 is set to the minimum 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 starting time of a given set of activities. In this context one can use the πš–πš’πš—πš’πš–πšžπš– constraint to get the minimum starting time of a set of tasks.

Remark

Note that πš–πš’πš—πš’πš–πšžπš– is a constraint and not just a function that computes the minimum 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

min in Choco, min in Gecode, min in JaCoP, minimum in SICStus.

Used in

πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš—, πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš, πš—πšŽπš‘πš_πšπš›πšŽπšŠπšπšŽπš›_πšŽπš•πšŽπš–πšŽπš—πš.

See also

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

comparison swapped: πš–πšŠπš‘πš’πš–πšžπš–.

generalisation: πš–πš’πš—πš’πš–πšžπš–_πš–πš˜πšπšžπš•πš˜Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš).

implied by: πšŠπš—πš.

implies: πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘, πš’πš—.

soft variant: πš–πš’πš—πš’πš–πšžπš–_πšŽπš‘πšŒπšŽπš™πš_0Β (value 0 is ignored), πš˜πš™πšŽπš—_πš–πš’πš—πš’πš–πšžπš–Β (open constraint).

specialisation: πš–πš’πš—_πš—Β (minimum or order πš— replaced by absolute minimum).

Keywords

characteristic of a constraint: minimum, maxint, automaton, automaton without counters, reified automaton constraint.

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

constraint type: order constraint.

filtering: arc-consistency.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β‹πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›<πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŽπ‘πƒπ„π‘(0,π™Όπ™°πš‡π™Έπ™½πšƒ,πšŸπšŠπš›)=𝙼𝙸𝙽

Graph model

The condition πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’ holds if and only if πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2 corresponds to the same vertex. It is used in order to enforce to keep all the vertices of the initial graph. πŽπ‘πƒπ„π‘(0,π™Όπ™°πš‡π™Έπ™½πšƒ,πšŸπšŠπš›) refers to the source vertices of the graph, i.e., those vertices that do not have any predecessor.

PartsΒ (A) andΒ (B) of FigureΒ 5.217.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŽπ‘πƒπ„π‘ graph property, the vertices of rank 0 (without considering the loops) of the final graph are outlined with a thick circle.

Figure 5.217.1. Initial and final graph of the πš–πš’πš—πš’πš–πšžπš– constraint
ctrs/minimumActrs/minimumB
(a) (b)
Automaton

FigureΒ 5.217.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.217.2. Automaton of the πš–πš’πš—πš’πš–πšžπš– constraint
ctrs/minimum1
Figure 5.217.3. Hypergraph of the reformulation corresponding to the automaton of the πš–πš’πš—πš’πš–πšžπš– constraint
ctrs/minimum2