Sets as Sequences: Ordered Sets

Introduction

Sets are introduced in chapter Set Definition. There we state that in general, sets in GAMS are regarded as an unordered collection of labels. However, in some contexts, say, multi-period planning models, some sets need to be treated as if they were sequences. In this chapter we will establish the notion of ordered sets and we will cover their special features and the associated operations.

Examples where ordered sets are needed include economic models that explicitly represent conditions in different time periods that are linked, location problems where the formulation may require a representation of contiguous areas, as in a grid representation of a city, scheduling problems and programs that model stocks of capital with equations of the form 'stocks at the end of period \(n\) are equal to stocks at the end of period \(n-1\) plus net gains during period \(n\)'.

Note
Models involving sequences of time periods are often called dynamic models, because they describe how conditions change over time. This use of the word dynamic unfortunately has a different meaning from that used in connection with dynamic sets, but this is unavoidable.

Ordered and Unordered Sets

Certain one-dimensional sets may be treated as if they were a sequence. Those sets need to be ordered and static. A one-dimensional set is ordered if the definition or initialization of the elements in the set corresponds to the order of the labels in the GAMS Entry order.

Note
  • The GAMS entry order is the order in which the individual labels first appear in the GAMS program, either explicitly or as a result of using the shorthand asterisk notation.
  • For the sake of simplicity, sets that are static and ordered are often just referred to as ordered sets.

GAMS maintains a unique element list where all labels that are used as elements in one or more sets are listed. The order of the elements in any one set is the same as the order of those elements in the unique element list. This means that the order of a set may not be what it appears to be if some of the labels were used in an earlier definition. The internal GAMS order of the labels can be made visible with the dollar control option $onUELlist. This directive generates a map that is shown in the compilation output of the listing file. For details on the listing file and GAMS output in general, see chapter GAMS Output. A good rule of thumb is that if the user wants a set to be orderd and the labels in the set have not been used already, then they will be ordered.

In the example below we show ordered and unordered sets and the map showing the order. The input is:

$onUELlist
Set    t1  / 1987, 1988, 1989, 1990, 1991 /
       t2  / 1983, 1984, 1985, 1986, 1987 /
       t3  / 1987, 1989, 1991, 1983, 1985 / ;

Note that the label "1987" is the first label seen by GAMS. It appears again as the last label in the initialization list for the set t2. This means that the set t2 is not ordered and any attempt to use t2 in a context implying order, such as the operations introduced later in this chapter, will cause error messages. Observe that the set t3 is ordered, as all the members of t3 have appeared in the GAMS program before, and in the same order that they are listed in the definition of t3.

The unique element listing map below shows the entry order (the important one) and the sorted order, obtained by sorting the labels into dictionary order. The single digits on the left are the sequence numbers of the first label on that line.

G e n e r a l   A l g e b r a i c   M o d e l i n g   S y s t e m
Unique Element Listing

Unique Elements in Entry Order
    1   1987       1988       1989       1990       1991      1983
    7   1984       1985       1986

Unique Elements in Sorted Order
    1   1983       1984       1985       1986       1987      1988
    7   1989       1990       1991

A set can always be made ordered by moving its declaration closer to the beginning of the program. With these restrictions in mind, we will continue in the next section with the operations that may be used with ordered sets.

Sorting a Set

Note that besides the entry order of unique elements there is also a sorted (aphabetical) order. To obtain the sorted order (of an ordered or unordered set) the special predefined two-dimensional set SortedUELs(*,*) can be used. Consider the following example where set j is reported in an alphabetically sorted format:

set j / c, a, b, 1, 2, 11 /;
display j;
alias(*,u);
file ordered /ordered.txt/;
loop(SortedUels(u,j), put ordered j.tl:0 '  ');
putclose ordered;

The output generated by the display statement follows:

----      2 SET j  

c ,    a ,    b ,    1 ,    2 ,    11

Note that, as expected, the display statement shows the elements of set j in the entry order not in alphabetical order. However, the elements are listed in alphabetical order in the file ordered.txt. Note furthermore, that alphabetical sorting leads to an order where e.g. 11 precedes 2.

1  11  2  a  b  c

In the example above u is aliased with the Universal Set. For an introduction to writing external files with put, see chapter The Put Writing Facility.

Ord and Card Operators

As stated in section Labels in chapter GAMS Programs, labels in GAMS do not have a numerical value. The examples used were that the label '1986' does not have a numerical value of 1986 and the label '01' is different from the label '1'. This section introduces two operators - ord and card - that return integer values when applied to sets. While the integer values returned do not represent the numerical value of the label, they can be used for the same purpose.

Note
GAMS provides some string manipulation capability by extending the card and ord operators to also work on strings.

The Ord Operator

The operator ord returns the relative position of a member in a set.

Attention
By default the operator ord may be used only with one-dimensional sets that are static and ordered.

Some examples show the usage.

Set       t      "time periods"  / 1985*1995 / ; 
Parameter val(t) ;
val(t)  =  ord(t);

Note that as a result of the statements above, the value of val('1985') will be 1, val('1986') will be 2 and so on.

A common use of ord is in setting up vectors that represent quantities growing in some analytically specified way. For example, suppose a country has 56 million people in the base period and the population is growing at the rate of 1.5 percent per year. Then the population in succeeding years can be calculated as follows:

population(t)  =  56*(1.015**(ord(t) - 1)) ;

It is often useful to simulate general matrix operations in GAMS. The first index of a two dimensional parameter can conveniently represent the rows, the second the columns and order is necessary. The example below shows how to set the upper triangle of a matrix equal to the row index plus the column index, and the diagonal and lower triangle to zero.

Set       i       "row and column labels"        / x1*x10 /;
alias (i,j);
Parameter a(i,j)  "a general square matrix";
a(i,j) $ (ord(i) < ord(j)) = ord(i) + ord(j);

Note that in the assignment statement the logical condition (ord(i) < ord(j)) restricts the assignment to the entries of the upper triangle. For more information on logical conditions and conditional assignments in GAMS, see sections Logical Conditions and Conditional Assignments respectively.

Note that the strict requirement that the set needs to be ordered for the operator ord to be used may be relaxed with a dollar control option called offOrder. Consider the following lines where we revisit the example from the previous section.

$offOrder
Set       t1    / 1987, 1988, 1989, 1990, 1991 /
          t2    / 1983, 1984, 1985, 1986, 1987 /;
Parameter p(t2);
p(t2) = ord(t2);
display p;

Note that, as we explained above, the set t2 is not ordered. Therefore using ord(t2) somewhere in the model will usually cause the program to be terminated with an error message. However, with the dollar control option offOrder active, the set t2 is treated as if it were ordered and the display statement will generate the following output:

----      6 PARAMETER p  
1987 1.000,    1983 2.000,    1984 3.000,    1985 4.000,    1986 5.000

While this may be useful in some circumstances, the option comes with a price, since the system will not be able to diagnose odd and incorrect formulations and data sets. The strict requirement that the set needs to be ordered for the ord operator can be turned on again via onOrder.

The Card Operator

The operator card returns the number of elements in a set.

Note
The operator card may be used with any set: static and dynamic sets, ordered and unordered sets.

The following example illustrates its use:

Set    t  "time periods"  / 1985*1995 /;
Scalar s;
s  =  card(t);
Display s;

Note that s will be assigned the value 11 since the set t has 11 elements.

A common use of card is to specify some condition only for the final period, for example to fix a variable. Consider the following artificial example:

c.fx(t)$(ord(t) = card(t)) = demand(t);

Note that the logical condition (ord(t) = card(t)) restricts the assignment to the last element of the set t: no assignment is made for other members of t. The advantage of this way of fixing the variable c is that the membership of t can be changed safely and this statement will always fix c for the last element. For more information on logical conditions and conditional assignments in GAMS, see sections Logical Conditions and Conditional Assignments respectively.

Lag and Lead Operators

Lag and lead operators are used to relate the current member of an ordered set to the previous or next member of the set. GAMS provides two forms of lag and lead operators (linear and circular), they are summarized in Table 1. Note that in the table below t is a member of an ordered set and n is a positive integer.

Operation Symbol Description
Linear Lag t - n Refers to the element of the ordered set whose relative position in the set is ord(t)-n.
Linear Lead t + n Refers to the element of the ordered set whose relative position in the set is ord(t)+n.
Circular Lag t -- n Same as t - n, only here the first element of the set is assumed to be preceded by the last element of the set, thus forming a circle of elements.
Circular Lead t ++ n Same as t + n, only here the last element of the set is assumed to be followed by the first element of the set, thus forming a circle of elements.

Table 1: Linear and Circular Lag and Lead Operators

Note that the only difference between linear and circular lag and lead operators is how endpoints are treated. Linear operators assume that there are no members preceding the first and following the last member of the ordered set. This assumption may result in elements of the set being referenced that actually do not exist. Therefore the user must think carefully about the treatment of endpoints: models with linear lag and lead operators will need special exception handling logic to deal with them. The next two sections will describe how this issue is handled in GAMS in the context in which these operators are typically used: assignments and equations. Linear lag and lead operators are useful for modeling time periods that do not repeat, like a set of years (say 1990 to 1997).

Circular lag and lead operators assume that the first and last members of the set are adjacent, so as to form a circular sequence of members. This means that 'first--1' is a reference to 'last' and 'last++2' is the same as 'first++1'. All references and assignments are defined. The assumption of circularity is useful for modeling time periods that repeat, such as months of the year or hours in the day. It is quite natural to think of January as the month following December. Agricultural farm budget models and workforce scheduling models are examples of applications where circular leads occur naturally.

Note
  • GAMS is able to distinguish the linear lag and lead operators '-' and '+' from arithmetic operators by context. To avoid ambiguity, GAMS does not allow to mix lag and lead operators with arithmetic operators. For example, i+1+1 is not allowed, but writing i+(1+1) would work.
  • Observe that the lag (or lead) value n does not have to be an explicit constant: it can be an arbitrary expression, provided that it evaluates to an integer. If it does not, error messages will be produced. A negative result causes a switch in sense (from lag to lead, for example).

Note that if lag and lead operators are used with an unordered set, the program will terminate with an error message. The strict requirement that the set be ordered may be relaxed with the dollar control option offOrder. If the directive $offOrder is added, in the lines that follow unordered sets are treated as if they were ordered and therefore lag and lead operators may be used with them. While this may be advantageous in some circumstances, the option comes with a price, since the system will not be able to diagnose odd and incorrect formulations and data sets. The strict requirement that the set needs to be ordered for the use of lag and lead operators can be turned on again via onOrder.

The next two subsections will give some illustrative examples on the use of lag and lead operators in assignment statements and in equations respectively.

Lags and Leads in Assignments

Lag and lead operators may be used in assignment statements. The use of a lag or lead operator on the right-hand side of an assignment is called a reference, while their use on the left-hand side is called an assignment and involves the definition of a domain of the assignment. The concepts behind reference and assignment are equally valid for the linear and circular forms of the lag and lead operators. However, the importance of the distinction between reference and assignment is not pronounced for circular lag and lead operators, because non-existent elements are not referred to in this case.

Note
A reference to a non-existent element causes the default value zero to be used, whereas an attempt to assign to a non-existent element results in no assignment being made.

We will first illustrate linear lag and lead operators for reference and assignment. Then we will turn to the circular form of the operators.

Linear Lag and Lead Operators in Assignments - Reference

Consider the following example, where the lag operator is used on the right-hand side of an assignment statement:

Set       t             "time sequence"  / y-1987*y-1991 /;
Parameter a(t), b(t);
a(t)  =  1986 + ord(t);
b(t)  =  -1;
b(t)  =  a(t-1);
option decimals = 0;
display a, b;

Note that the option statement suppresses the decimal places from the display statement.

----      7 PARAMETER a  
y-1987 1987,    y-1988 1988,    y-1989 1989,    y-1990 1990,    y-1991 1991

----      7 PARAMETER b  
y-1988 1987,    y-1989 1988,    y-1990 1989,    y-1991 1990

Note that, as expected, the values for the parameter a are 1987, 1988 up to 1991 corresponding to the labels "y-1987", "y-1988" and so on. Observe that the parameter b is initialized to \(-1\) so that the result of the next assignment can be seen clearly. Note that in the last assignment the lag operator '-' is used on the right-hand side, resulting in the values for b to equal the values for a from the previous period. If there is no previous period, as with the first element, "y-1987", the value zero is assigned, replacing the previous value of \(-1\) (values of zero for parameters are not displayed).

Linear Lag and Lead Operators in Assignments - Assignment

Consider the following variation of the previous example. Here the lead operator is used on the left-hand side of an assignment statement:

Set       t            "time sequence"  / y-1987*y-1991 / ;
Parameter a(t), c(t) ;
a(t)    =  1986 + ord(t) ;
c(t)    =  -1;
c(t+2)  =  a(t) ;
option decimals = 0;
display a, c ;

Note that, as before, the option statement suppresses the decimal places from the display statement.

----      7 PARAMETER a  
y-1987 1987,    y-1988 1988,    y-1989 1989,    y-1990 1990,    y-1991 1991

----      7 PARAMETER c  
y-1987   -1,    y-1988   -1,    y-1989 1987,    y-1990 1988,    y-1991 1989

The assignment to a is explained in the previous subsection. Note that the parameter c is initialized to \(-1\). The assignment to c involving the lead operator on the left-hand side needs special attention. It is best to spell out step by step how this assignment is made. For each member of t in sequence, find the member of c associated with t+2. If it exists, replace its value with the value of a(t). If not (as with labels "y-1990" and "y-1991") make no assignment. The first member of the set t is "y-1987", therefore the first assignment is made to c("y-1989") which takes the value of a("y-1987"), that is 1987. No assignments at all are made to c("y-1987") and c("y-1988"): these two retain their previous values of \(-1\).

Circular Lag and Lead Operators in Assignments

The following example illustrates the use of circular lag and lead operators in assignment statements.

Set       s          "seasons" / spring, summer, autumn, winter /;
Parameter val(s)               / spring 10, summer 15, autumn 12, winter 8 /
          lagval(s)
          leadval(s);
lagval(s)     = -1 ;
lagval(s)     = val(s--2) ;
leadval(s)    = -1 ;
leadval(s++1) = val(s) ;
option decimals = 0;
display val, lagval, leadval;

Note that, as before, the option statement suppresses the decimal places from the display statement. The results are shown below.

-----     10 PARAMETER val  

spring 10,    summer 15,    autumn 12,    winter  8


----     10 PARAMETER lagval  

spring 12,    summer  8,    autumn 10,    winter 15


----     10 PARAMETER leadval  

spring  8,    summer 10,    autumn 15,    winter 12

In the example parameter lagval is used for reference while leadval is used for assignment. Notice that the case of circular lag and lead operators does not refer to any non-existent elements. The difference between reference and assignment is therefore not important. Note that the following two statements from the example above,

lagval(s)     = val(s--2) ;
leadval(s++1) = val(s) ;

are equivalent to

lagval(s++2)  = val(s) ;
leadval(s)    = val(s--1) ;

The use of reference and assignment have been reversed with no difference in effect.

Lags and Leads in Equations

The principles established in the previous section follow quite naturally into equation definitions. A lag or lead to the left of the '..' symbol is a modification of the domain of definition of the equation. The linear form may cause one or more individual equations to be suppressed. A lag or lead operation in the body of an equation (to the right of the '..' symbol) is a reference. If the associated label is not defined, the term vanishes.

Note
All lag and lead operands must be exogenous. For more information, see section Functions in Equation Definitions.

In the next two subsections we will provide examples illustrating the use of the linear form of the lag and lead operators in equations to modify the domain of definition and for reference respectively. In the last subsection we will turn to circular lag and lead operators in equations.

Linear Lag and Lead Operators in Equations - Domain Control

Consider the following simple artificial multi-period example. We specify a complete model and encourage users to solve it and further explore it.

Sets      t           / t1*t5 /
          tfirst(t);
Parameter i(t)        / #t 1 /;
Scalar    k0          / 3.00 /;

tfirst(t)  =  yes$(ord(t) = 1);

Variables k(t), z;
k.fx(tfirst) = k0;

Equations kk(t), dummy;
dummy..      z =e= 0;
kk(t+1)..    k(t+1) =e=  k(t) + i(t);

model m /all/;
option limrow = 10;
solve m using lp min z;

Note that the equation kk is declared over the set t, but it is defined over the domain (t+1). Therefore the first equation that will be generated is the following:

k('t2')  =e=  k('t1') + i('t1');

Note that the value of the variable k('t1') is fixed at the value of scalar k0. Observe that for the last element of t, the term k(t+1) is not defined and therefore the equation will not be generated. If lag or lead operators are used in the domain of definition of an equation, the equation listing can be a useful tool to verify whether the equations that have been generated are those that were intended:

kk(t2)..  - k(t1) + k(t2) =E= 1 ; (LHS = 0, INFES = 1 ****)     
kk(t3)..  - k(t2) + k(t3) =E= 1 ; (LHS = 0, INFES = 1 ****)   
kk(t4)..  - k(t3) + k(t4) =E= 1 ; (LHS = 0, INFES = 1 ****)     
kk(t5)..  - k(t4) + k(t5) =E= 1 ; (LHS = 0, INFES = 1 ****)

To summarize, the lead operator in the domain of definition has restricted the number of constraints generated so that there are no references to non-existent variables.

For a more realistic model that illustrates the usage of linear lag operators in equations, see for example the optimal economic growth model [RAMSEY].

Linear Lag and Lead Operators in Equations - Reference

In the previous subsection we showed how to write the equation kk using the lead operator for domain control in combination with fixing the variable k(tfirst) to k0. An alternative formulation could neglect the fixing of k(tfirst) and use a lag operator and a dollar condition in the body of the equation while the domain of definition is unrestricted:

kk(t)..  k(t) =e= k(t-1) + i(t-1) + k0$tfirst(t);

Note that for the first element of the set t the terms k(t-1) and i(t-1) are not defined and therefore vanish. Without the conditional term, the resulting equation would be:

k('t1') =e= 0;

However, this would lead to different results as k('t1') would not be set to the value of k0 anymore. Therefore the conditional expression k0$tfirst(t) is added. Observe that in this formulation equations are generated for all time periods, no equation is suppressed.

In general, the choice between using lag and lead operators as reference like in the last example or in domain control is often a matter of taste.

Circular Lag and Lead Operators in Equations

In the case of circular lag and lead operators, the difference between their use in domain control and as reference is not important because it does not lead to any equations or terms being suppressed. Consider the following artificial example.

Set      s        "seasons" / spring, summer, autumn, winter /;

Variable produ(s) "amount of goods produced in each season"
         avail(s) "amount of goods available in each season"
         sold(s)  "amount of goods sold in each season";

Equation matbal(s);

matbal(s)..  avail(s++1) =e= avail(s) + produ(s) - sold(s);

In this example four individual equations are generated. They are listed below.

avail('summer')  =e=  avail('spring') + produ('spring') - sold('spring');
avail('autumn')  =e=  avail('summer') + produ('summer') - sold('summer');
avail('winter')  =e=  avail('autumn') + produ('autumn') - sold('autumn');
avail('spring')  =e=  avail('winter') + produ('winter') - sold('winter');

Note that for the last element of the set s the term avail(s++1) is evaluated to avail('spring'). This term is well defined and therefore it does not vanish. Similarly, using the circular lead operator in the domain of definition like in the following line will result in the same four equations being generated as above and no equation being suppressed.

matbal(s++1)..  avail(s++1) =e= avail(s) + produ(s) - sold(s);

Summary

This chapter introduced the concept of ordered sets. All the features in GAMS that dealt with this issue including the ord and card functions, as well as the linear and circular forms of the lag and lead operators were described in detail.