## 5.217. minimum

 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 minimum value of the collection of domain variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

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

The $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint holds since its first argument $\mathrm{𝙼𝙸𝙽}=2$ is set to the minimum 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 starting time of a given set of activities. In this context one can use the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint to get the minimum starting time of a set of tasks.

Remark

Note that $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ is a constraint and not just a function that computes the minimum 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

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

Used in
See also

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

specialisation: $\mathrm{𝚖𝚒𝚗}_𝚗$ (minimum or order $𝚗$ replaced by absolute minimum).

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

The condition $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚔𝚎𝚢}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚔𝚎𝚢}$ holds if and only if $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}$ and $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}$ corresponds to the same vertex. It is used in order to enforce to keep all the vertices of the initial graph. $\mathrm{𝐎𝐑𝐃𝐄𝐑}\left(0,\mathrm{𝙼𝙰𝚇𝙸𝙽𝚃},\mathrm{𝚟𝚊𝚛}\right)$ 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 $\mathrm{𝐎𝐑𝐃𝐄𝐑}$ 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 $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint  (a) (b)
Automaton

Figure 5.217.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.217.2. Automaton of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint ##### Figure 5.217.3. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint 