## 5.262. minimum

Origin

CHIP

Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi Έ\pi ½},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonym

$\mathrm{\pi \pi \pi }$.

Arguments
 $\mathrm{\pi Ό\pi Έ\pi ½}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>0$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

$\mathrm{\pi Ό\pi Έ\pi ½}$ is the minimum value of the collection of domain variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Example
 $\left(2,β©3,2,7,2,6βͺ\right)$ $\left(7,β©8,8,7,8,7βͺ\right)$

The first $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint holds since its first argument $\mathrm{\pi Ό\pi Έ\pi ½}=2$ is set to the minimum value of the collection $\beta ©3,2,7,2,6\beta ͺ$.

Typical
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• All occurrences of two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be swapped.

• One and the same constant can be added to $\mathrm{\pi Ό\pi Έ\pi ½}$ as well as to the $\mathrm{\pi \pi \pi }$ attribute of all items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Arg. properties
• Functional dependency: $\mathrm{\pi Ό\pi Έ\pi ½}$ determined by $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

• Aggregate: $\mathrm{\pi Ό\pi Έ\pi ½}\left(\mathrm{\pi \pi \pi }\right)$, $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left(\mathrm{\pi \pi \pi \pi \pi }\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{\pi \pi \pi \pi \pi \pi \pi }$ constraint to get the minimum starting time of a set of tasks.

Remark

Note that $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ is a constraint and not just a function that computes the minimum value of a collection of variables: potential values of $\mathrm{\pi Ό\pi Έ\pi ½}$ influence the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$, and reciprocally potential values that can be assigned to variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ influence $\mathrm{\pi Ό\pi Έ\pi ½}$.

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint is called $\mathrm{\pi \pi \pi }$ in JaCoP (http://www.jacop.eu/).

Algorithm

A filtering algorithm for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint is described inΒ [Beldiceanu01].

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint is entailed if all the following conditions hold:

1. $\mathrm{\pi Ό\pi Έ\pi ½}$ is fixed.

2. At least one variable of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ is assigned value $\mathrm{\pi Ό\pi Έ\pi ½}$.

3. All variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ have their minimum value greater than or equal to value $\mathrm{\pi Ό\pi Έ\pi ½}$.

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

Number of solutions for $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$: 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{\pi \pi \pi \pi \pi \pi \pi }$: domains $0..n$

Systems

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

Used in

generalisation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\mathrm{mod}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$).

specialisation: $\mathrm{\pi \pi \pi }_\mathrm{\pi }$Β (minimum or order $\mathrm{\pi }$ replaced by absolute minimum).

Keywords
Cond. implications

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi Έ\pi ½},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Β Β Β  withΒ  $\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>\mathrm{\pi Ό\pi Έ\pi ½}$

Β Β Β  andΒ Β  $\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>\mathrm{\pi Ό\pi Έ\pi ½}$

Β Β implies $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}$$\left(\mathrm{\pi ³\pi ΄\pi Ώ\pi \pi ·},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$.

Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\beta \left(\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi ’}=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi ’},\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }<\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }\hfill \end{array}\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi \pi }$$\left(0,\mathrm{\pi Ό\pi °\pi \pi Έ\pi ½\pi },\mathrm{\pi \pi \pi }\right)=\mathrm{\pi Ό\pi Έ\pi ½}$

Graph model

The condition $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi ’}=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi ’}$ holds if and only if $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}$ and $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}$ corresponds to the same vertex. It is used in order to enforce to keep all the vertices of the initial graph. $\mathrm{\pi \pi \pi \pi \pi }\left(0,\mathrm{\pi Ό\pi °\pi \pi Έ\pi ½\pi },\mathrm{\pi \pi \pi }\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{\pi \pi \pi \pi \pi }$ graph property, the vertices of rank 0 (without considering the loops) of the final graph are outlined with a thick circle.

Automaton

FigureΒ 5.262.2 depicts a first counter free deterministic automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint. Let ${\mathrm{\pi  \pi °\pi }}_{i}$ be the ${i}^{th}$ variable of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. To each pair $\left(\mathrm{\pi Ό\pi Έ\pi ½},{\mathrm{\pi  \pi °\pi }}_{i}\right)$ corresponds a signature variable ${S}_{i}$ as well as the following signature constraint: $\left(\mathrm{\pi Ό\pi Έ\pi ½}<{\mathrm{\pi  \pi °\pi }}_{i}\beta {S}_{i}=0\right)\beta §\left(\mathrm{\pi Ό\pi Έ\pi ½}={\mathrm{\pi  \pi °\pi }}_{i}\beta {S}_{i}=1\right)\beta §\left(\mathrm{\pi Ό\pi Έ\pi ½}>{\mathrm{\pi  \pi °\pi }}_{i}\beta {S}_{i}=2\right)$.

FigureΒ 5.262.3 depicts a second counter free non deterministic automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint, where the argument $\mathrm{\pi Ό\pi Έ\pi ½}$ is also part of the sequence passed to the automaton.

FigureΒ 5.262.6 depicts a third deterministic automaton with one counter associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint, where the argument $\mathrm{\pi Ό\pi Έ\pi ½}$ is unified to the final value of the counter.