## 5.262. minimum

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)$ $\left(7,〈8,8,7,8,7〉\right)$

The first $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint holds since its first argument $\mathrm{𝙼𝙸𝙽}=2$ is set to the minimum value of the collection $〈3,2,7,2,6〉$.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Arg. properties
• Functional dependency: $\mathrm{𝙼𝙸𝙽}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• Aggregate: $\mathrm{𝙼𝙸𝙽}\left(\mathrm{𝚖𝚒𝚗}\right)$, $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left(\mathrm{𝚞𝚗𝚒𝚘𝚗}\right)$.

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

A filtering algorithm for the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint is described in [Beldiceanu01].

The $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint is entailed if all the following conditions hold:

1. $\mathrm{𝙼𝙸𝙽}$ is fixed.

2. At least one variable of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ is assigned value $\mathrm{𝙼𝙸𝙽}$.

3. All variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ have their minimum value greater than or equal to value $\mathrm{𝙼𝙸𝙽}$.

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

Number of solutions for $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$: domains $0..n$  Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

0537369465170993127360926269505
131917521013103154360711012415
21765781115292018114085185
3-1152113367617411288991
4--13166514197325089
5---163205958975
6----11276305
7-----1255
8------1

Solution count for $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$: domains $0..n$  Systems

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

Used in

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

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

Keywords
Cond. implications

$\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}\left(\mathrm{𝙼𝙸𝙽},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $\mathrm{𝚏𝚒𝚛𝚜𝚝}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>\mathrm{𝙼𝙸𝙽}$

and   $\mathrm{𝚕𝚊𝚜𝚝}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>\mathrm{𝙼𝙸𝙽}$

implies $\mathrm{𝚍𝚎𝚎𝚙𝚎𝚜𝚝}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(\mathrm{𝙳𝙴𝙿𝚃𝙷},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$.

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.262.1 respectively show the initial and final graph associated with the first example of 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.262.1. Initial and final graph of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint  (a) (b)
Automaton

Figure 5.262.2 depicts a first counter free deterministic 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 ${S}_{i}$ as well as the following signature constraint: $\left(\mathrm{𝙼𝙸𝙽}<{\mathrm{𝚅𝙰𝚁}}_{i}⇔{S}_{i}=0\right)\wedge \left(\mathrm{𝙼𝙸𝙽}={\mathrm{𝚅𝙰𝚁}}_{i}⇔{S}_{i}=1\right)\wedge \left(\mathrm{𝙼𝙸𝙽}>{\mathrm{𝚅𝙰𝚁}}_{i}⇔{S}_{i}=2\right)$.

##### Figure 5.262.2. Counter free automaton of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint ##### Figure 5.262.3. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint Figure 5.262.3 depicts a second counter free non deterministic automaton associated with the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint, where the argument $\mathrm{𝙼𝙸𝙽}$ is also part of the sequence passed to the automaton.

##### Figure 5.262.4. Counter free non deterministic automaton of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$$\left(\mathrm{𝙼𝙸𝙽},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$ constraint assuming that the union of the domain of the variables is the set $\left\{1,2,3,4\right\}$ and that the elements of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are first passed to the automaton followed by $\mathrm{𝙼𝙸𝙽}$ (state ${s}_{i}$ means that no value strictly less than value $i$ was found and that value $i$ was already encountered at least once) ##### Figure 5.262.5. Hypergraph of the reformulation corresponding to the counter free non deterministic automaton of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint Figure 5.262.6 depicts a third deterministic automaton with one counter associated with the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint, where the argument $\mathrm{𝙼𝙸𝙽}$ is unified to the final value of the counter.

##### Figure 5.262.6. Automaton (with one counter) of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint and its glue matrix ##### Figure 5.262.7. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint: since all states variables ${Q}_{0},{Q}_{1},\cdots ,{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 