5.209. min_index

Origin

N. Beldiceanu

Constraint

min_index​(MIN_INDEX,​VARIABLES)​

Argument(s)

MIN_INDEX	dvar
VARIABLES	collection​(index−int,​var−dvar)​

Restriction(s)

|VARIABLES|>​0

MIN_INDEX≥0

MIN_INDEX≤|VARIABLES|

required​(VARIABLES,​​[index,​var]​)​

VARIABLES.index≥1

VARIABLES.index≤|VARIABLES|

distinct​(VARIABLES,​index)​

Purpose

MIN_INDEX is the index of the variables corresponding to the minimum value of the collection of variables VARIABLES.

Example

( 2,​〈 index−1 var−3,​ index−2 var−2,​ index−3 var−7,​ index−4 var−2,​ index−5 var−6 〉 )

( 4,​〈 index−1 var−3,​ index−2 var−2,​ index−3 var−7,​ index−4 var−2,​ index−5 var−6 〉 )

The attribute var=2 of the second and fourth items of the collection VARIABLES is the minimum value over values 3,​2,​7,​2,​6. Consequently, both min_index constraints hold since their first arguments MIN_INDEX are respectively set to 2 and 4.

Usage

Within the context of scheduling, assume the variables of the VARIABLES collection correspond to the starts of a set of tasks. Then MIN_INDEX gives the indexes of those tasks that can be scheduled first.

See also

max_index.

Key words

characteristic of a constraint: minimum.

constraint type: order constraint.

Arc input(s)

VARIABLES

Arc generator

CLIQUE↦collection​(variables1,​variables2)​

Arc arity

2

Arc constraint(s)

variables1.key=variables2.key∨variables1.var​<variables2.var

Graph property(ies)

ORDER​(0,​0,​index)​=MIN_INDEX

---

Graph model

Parts (A) and (B) of Figure 5.209.1 respectively show the initial and final graph associated with the two examples of the Example slot. Since we use the ORDER graph property, the vertices of rank 0 (without considering the loops) of the final graph are outlined with a thick circle.

Figure 5.209.1. Initial and final graph of the min_index constraint

(a)	(b)