3.3 Indexing expressions and dummy indices

Indexing expression is an auxiliary construction, which specifies a plain set of n-tuples and introduces dummy indices. It has two syntactic forms:

{ entry-1, entry-2, …, entry-m }

{ entry-1, entry-2, …, entry-m : predicate }

where entry-1, entry-2, …, entry-m are indexing entries, predicate is a logical expression which specifies an optional predicate.

Each indexing entry in the indexing expression has one of the following three forms:

t in S

(t1, t2, …, tk) in S

S

where t1, t2, …, tk are indices, S is a set expression (discussed in the next section), which specifies the basic set.

The number of indices in the indexing entry must be the same as the dimension of the basic set S, i.e. if S consists of 1-tuples, the first form must be used, and if S consists of n-tuples, where n > 1, the second form must be used.

If the first form of the indexing entry is used, the index t can be a dummy index only. If the second form is used, the indices t1, t2, …, tk can be either dummy indices or some numeric or symbolic expressions, where at least one index must be a dummy index. The third, reduced form of the indexing entry has the same effect as if there were t (if S is 1-dimensional) or t1, t2, …, tk (if S is n-dimensional) all specified as dummy indices.

Dummy index is an auxiliary model object, which acts like an individual variable. Values assigned to dummy indices are components of n-tuples from basic sets, i.e. some numeric and symbolic quantities.

For referencing purposes dummy indices can be provided with symbolic names. However, unlike other model objects (sets, parameters, etc.) dummy indices do not need to be explicitly declared. Each undeclared symbolic name being used in the indexing position of an indexing entry is recognized as the symbolic name of corresponding dummy index.

Symbolic names of dummy indices are valid only within the scope of the indexing expression, where the dummy indices were introduced. Beyond the scope the dummy indices are completely inaccessible, so the same symbolic names may be used for other purposes, in particular, to represent dummy indices in other indexing expressions.

The scope of indexing expression, where implicit declarations of dummy indices are valid, depends on the context, in which the indexing expression is used:

1. If the indexing expression is used in iterated operator, its scope extends until the end of the integrand.
2. If the indexing expression is used as a primary set expression, its scope extends until the end of this indexing expression.
3. If the indexing expression is used to define the subscript domain in declarations of some model objects, its scope extends until the end of the corresponding statement.

The indexing mechanism implemented by means of indexing expressions is best explained by some examples discussed below.

Let there be three sets:

A = {4, 7, 9}

B = {(1,Jan), (1,Feb), (2,Mar), (2,Apr), (3,May), (3,Jun)}

C = {a, b, c}

where A and C consist of 1-tuples (singles), B consists of 2-tuples (doubles). And consider the following indexing expression:

{i in A, (j,k) in B, l in C}

where i, j, k, and l are dummy indices.

Although MathProg is not a procedural language, for any indexing expression an equivalent algorithmic description could be given. In particular, the algorithmic description of the indexing expression above is the following:

for all i in A do
   for all (j,k) in B do
      for all l in C do
         action;

where the dummy indices i, j, k, l are consecutively assigned corresponding components of n-tuples from the basic sets A, B, C, and action is some action that depends on the context, where the indexing expression is used. For example, if the action were printing current values of dummy indices, the output would look like follows:

i = 4	j = 1	k = Jan	l = a
i = 4	j = 1	k = Jan	l = b
i = 4	j = 1	k = Jan	l = c
i = 4	j = 1	k = Feb	l = a
i = 4	j = 1	k = Feb	l = b
…	…	…	…
i = 9	j = 3	k = Jun	l = b
i = 9	j = 3	k = Jun	l = c

Let the example indexing expression be used in the following iterated operation:

sum{i in A, (j,k) in B, l in C} p[i,j,k,l]

where p[i, j, k, l] may be a 4-dimensional numeric parameter or some numeric expression whose resultant value depends on i, j, k, and l. In this case the action is summation, so the resultant value of the primary numeric expression is the sum of p[i, j, k, l], where summation is performed over all i in A, (j,k) in B, and l in C.

Now let the example indexing expression be used as a primary set expression. In this case the action is gathering all 4-tuples (quadruples) of the form (i, j, k, l) in one set, so the resultant value of such operation is simply the Cartesian product of the basic sets:

A x B x C = {(i,j,k,l) : i in A, (j,k) in B, l in C}

Note that in this case the same indexing expression might be written in the reduced form:

{A, B, C}

because the dummy indices i, j, k, and l are not referenced and therefore their symbolic names are not needed.

Finally, let the example indexing expression be used as the subscript domain in the declaration of a 4-dimensional model object, say, a numeric parameter:

par p{i in A, (j,k) in B, l in C} ... ;

In this case the action is generating the parameter members, where each member has the form p[i, j, k, l].

As was said above, some indices in the second form of indexing entries may be numeric or symbolic expressions, not only dummy indices. In this case resultant values of such expressions play role of some logical conditions to select only that n-tuples from the Cartesian product of basic sets, which satisfy these conditions.

Consider, for example, the following indexing expression:

{i in A, (i-1,k) in B, l in C}

where i, k, l are dummy indices, and i-1 is a numeric expression. The algorithmic decsription of this indexing expression is the following:

for all i in A do
   for all (j,k) in B and j = i-1 do
      for all l in C do
         action;

Thus, if this indexing expression were used as a primary set expression, the resultant set would be the following:

{(4,May,a), (4,May,b), (4,May,c), (4,Jun,a), (4,Jun,b), (4,Jun,c)}.

Should note that in this case the resultant set consists of 3-tuples, not of 4-tuples, because in the indexing expression there is no dummy index that corresponds to the first component of 2-tuples from the set B.

The general rule is: the number of components of n-tuples defined by an indexing expression is the same as the number of dummy indices in that indexing expression, where the correspondence between dummy indices and components on n-tuples in the resultant set is positional, i.e. the first dummy index corresponds to the first component, the second dummy index corresponds to the second component, etc.

In many cases it is needed to select a subset from the Cartesian product of some sets. This may be attained by using an optional logical predicate, which is specified in indexing expression after the last or the only indexing entry.

Consider, for another example, the following indexing expression:

{i in A, (j,k) in B, l in C: i <= 5 and k <> 'Mar'}

where the logical expression following the colon is a predicate. The algorithmic description of this indexing expression is the following:

for all i in A do
   for all (j,k) in B do
      for all l in C do
         if i <= 5 and k != 'Mar' then
            action;

Thus, if this indexing expression were used as a primary set expression, the resultant set would be the following:

{(4,1,Jan,a), (4,1,Feb,a), (4,2,Apr,a), …, (4,3,Jun,c)}.

If no predicate is specified in the indexing expression, the one, which takes on the value true, is assumed.