Dynamic Sets

Introduction

Sets in general are covered in chapter Set Definition. In this chapter we introduce a special type of sets: dynamic sets. The sets that we discuss in detail in chapter Set Definition have their elements stated at compile time (e.g. enclosed in slashes at the set declaration or when loading a set from gdx via $load) and during execution time the membership is never changed. Therefore they are called static sets. In contrast, the elements of dynamic sets are not fixed, but may be added and removed during execution of the program. Dynamic sets are most often used as controlling indices in assignments or equation definitions and as the conditional set in a dollar-controlled indexed operation. We will first show how assignments are used to change set membership in dynamic sets. Then we will introduce set operations and the last part of this chapter covers dynamic sets in the context of dollar conditions.

Assigning Membership to Dynamic Sets

Dynamic Sets may be assigned to in a similar way as other data types. There are only two possible values: yes and no. Note that arithmetic operations cannot be performed on sets in the same way as on value typed identifiers (parameters, variables and equations subtypes). However, there are special set operations.

The Syntax

Like any other set, a dynamic set has to be declared before it may be used in the model. Often, a dynamic set is declared as subset of a static set. Dynamic sets in GAMS may also be multi-dimensional like static sets. The maximum number of permitted dimensions follows the rules of the basic Data Types and Definitions. For multi-dimensional dynamic sets the index sets can also be specified explicitly at declaration. That way dynamic sets are domain checked. Of course it is also possible to use dynamic sets that are not domain checked. This provides additional power and flexibility but also a lack of intelligibility and danger. Any label is legal as long as such a set's dimension, once established, is preserved.

In general, the syntax for assigning membership to dynamic sets in GAMS is:

set_name(index_list | label) = yes | no ;

Set_name is the internal name of the set in GAMS, index_list refers to the domain of the dynamic set and label is one specific element of the domain. An assignment statement may assign membership to the dynamic set either to the whole domain or to a subset of the domain or to one specific element. Note that, as usual, a label must appear in double or single quotes. Yes and no are keywords in GAMS. They are used to add members to or remove them from the dynamic set. Examples are given in the following subsections.

Illustrative Example

Throughout this chapter we will use examples adapted from the database model [ZLOOF] to illustrate the introduced concepts. Here we start with assignments of membership to dynamic sets.

Set  item            "all items"              / dish, ink, lipstick, pen, pencil, perfume /
     subitem1(item)  "first subset of item"   / pen, pencil /
     subitem2(item)  "second subset of item";

subitem1('ink')      = yes ;
subitem1('lipstick') = yes ;
subitem2(item)       = yes  ;
subitem2('perfume')  = no ;
display subitem1, subitem2;

Note that the sets subitem1 and subitem2 are declared like any other set. The two sets become dynamic as soon as they are assigned to a few lines later. They are also domain checked: the only members they will ever be able to have must also be members of the set item. The first assignment not only makes the set subitem1 dynamic, it also has the effect that its superset item becomes a static set and from then on its membership is frozen. The first two assignments each add one new element to subitem1. Note that both are also elements of item, as required. The third assignment is an example of the familiar indexed assignment: subitem2 is assigned all the members of item. The last assignment removes the label 'perfume' from the dynamic set subitem2. The output generated by the display statement is shown below:

----      9 SET subitem1  first subset of item

ink     ,    lipstick,    pen     ,    pencil  


----      9 SET subitem2  second subset of item

dish    ,    ink     ,    lipstick,    pen     ,    pencil  

Note that even though the labels 'pen' and 'pencil' were declared to be members of the set subitem1 before the assignment statements that added the labels 'ink' and 'lipstick' to the set, they appear in the listing above at the end. The reason is that elements are displayed in the internal order, which in this case is the order specified in the declaration of the set item.

Alternatively, the elements of the set subitem2 could be assigned in the following way:

subitem2(item)     = no;
subitem2(subitem1) = yes;
subitem2('dish')   = yes;

The first statement removes all elements from the set subitem2. The second statement adds all elements of the set subitem1. Note that this assignment is permitted since the set subitem1 is a proper subset of the set item (which is the domain of subitem2). The third statement adds one additional element.

Dynamic Sets with Multiple Indices

As mentioned earlier, dynamic sets may be multi-dimensional. The following lines continue the example above and illustrate assignments for multi-dimensional sets.

Sets sold(item)        "items sold" / pencil, pen /
     sup               "suppliers"  / bic, parker, waterman /
     supply(sold,sup) ;

supply('pencil','bic')  = yes ;
supply('pen',sup)       = yes ;

Note that supply is a two-dimensional dynamic set. It links sold items with their respective suppliers. Other examples with multi-dimensional dynamic sets are in subsections Dynamic Sets in Conditional Assignments and Conditional Indexed Operations with Dynamic Sets below.

All the mechanisms using asterisks and parenthesized lists that were introduced in section Multi-Dimensional Sets in chapter Set Definition are available for dynamic sets as well.

Equations Defined over the Domain of Dynamic Sets

Generally, dynamic sets are not permitted as domains in declarations of sets, variables, parameters and equations. However, they may be referenced and sometimes it is necessary to define an equation over a dynamic set.

Note
The trick is to declare the equation over the entire domain but define it over the dynamic set.

For example, defining an equation over a dynamic set can be necessary in models that will be solved for arbitrary groupings of regions simultaneously. We assume there are no explicit links between regions, but that we have a number of independent models with a common data definition and common logic. We illustrate with an artificial example, leaving out lots of details.

Set        allr            "all  regions"  /  N, S, W, E, N-E, S-W  /
           r(allr)         "region subset for particular solution"
           type            "set for various types of data" ;

Scalar     price                         /10/ ;
Parameter  revenue(allr);
Table      data(allr,type) "all other data ..." ;

Variables  activity1(allr) "first activity"
           activity2(allr) "second activity"
           revenue(allr)   "revenue"          ;

Equations  resource1(allr) "first resource constraint ..."
           prodbal1(allr)  "first production balance ..." ;

resource1(r)..  activity1(r)       =l=  data(r,'resource-1');
prodbal1(r)..   activity2(r)*price =e= revenue(r) ;

To repeat the important point: the equation is declared over the set allr, but defined over r, a subset. Note that the variables and data are declared over allr but referenced over r. Then the set r may be assigned arbitrary combinations of elements of the set allr, and the model may be solved any number of times for the chosen groupings of regions.

Assigning Membership to Singleton Sets

Singleton sets have only one element. Hence any assignment to a singleton set first clears or empties the set, no explicit action to clear the set is necessary. This is illustrated with the following example:

Set            i     "Static Set"            / a, b, c /
               ii(i) "Dynamic Set"           /    b    /;
Singleton Set  si(i) "Dynamic Singleton Set" /    b    /;

ii('c') = yes;
si('c') = yes;
display ii, si;

Note that both ii and si are subsets of the set i, but only si is declared as a singleton set. The assignment statements assign to both sets the element 'c'. While 'c' is added to the set ii, it replaces the original element in the singleton set si. The output from the display statement confirms this:

----      8 SET ii  Dynamic Set
b,    c

----      8 SET si  Dynamic Singleton Set
c

For more information on singleton sets in GAMS, see section Singleton Sets.

Attention
That an assignment to a singleton set first clears the set always, means that it is even cleared if there would be no change at all for a regular set:
Singleton Set s / 1 /;
s(s)$0 = yes;
display s;

Here is the output from the display statement in the listing file:

----      3 SET s  

                                                      ( EMPTY )

The assignment behavior can be changed with the option and command line parameter strictSingleton which affects the behavior of a membership assignment to a Singleton Set. With strictSingleton=0 GAMS does not complain about an assignment with more than one element on the right hand side but takes the first one. With strictSingleton=1 (default), such an assignment raises an error. Consider the following example:

Set            i     "Static Set"            / a, b, c /
Singleton Set  si(i) "Dynamic Singleton Set";
si(i) = ord(i) > 1;
display si;

By default, the above code will trigger an error as an assignment to a singleton set with more than one element on the right hand side is forbidden:

*** Error at line 3: Multiple assignment to Singleton Set not allowed (see option strictSingleton)

However, with option (or command line parameter) strictSingleton=0 GAMS does not complain about such an assignment with more than one element on the right hand side but takes the first one:

Set            i     "Static Set"            / a, b, c /
Singleton Set  si(i) "Dynamic Singleton Set";
option strictSingleton = 0;
si(i) = ord(i) > 1;
display si;

The output from the display statement confirms this:

----      5 SET si  Dynamic Singleton Set

b

Set Operations

GAMS provides symbols for arithmetic set operations that may be used with dynamic sets. An overview of the set operations in GAMS is given in Table 1. Examples and alternative formulations for each operation follow. Note that in the table below the set i is the static superset and the sets j and k are dynamic sets.

Set Operation Operator Description
Set Union j(i) + k(i) Returns a subset of i that contains all the elements of the sets j and k.
Set Intersection j(i) * k(i) Returns a subset of i that contains the elements of the set j that are also elements of the set k.
Set Complement not j(i) Returns a subset of i that contains all the elements of the set i that are not elements of the set j.
Set Difference j(i) - k(i) Returns a subset of i that contains all the elements of the set j that are not elements of the set k.

Table 1: Set Operations with Dynamic Sets

The following examples draw on the database model [ZLOOF] that we introduced above. Recall that the set item is the superset of the dynamic sets subitem1 and subitem2. We add new dynamic sets for the results of the respective set operations. The following example illustrates that the dynamic set operations are equivalent to the following alternative ways of representation.

Sets union1(item), intersection1(item), complement1(item), difference1(item)
     union2(item), intersection2(item), complement2(item), difference2(item);

union1(item) = subitem1(item) + subitem2(item); display union1;
union2(subitem1) = yes; union2(subitem2) = yes; display union2;

intersection1(item) = subitem1(item) * subitem2(item);          display intersection1;
intersection2(item) = yes$(subitem1(item) and subitem2(item));  display intersection2;

complement1(item) = not subitem1(item);              display complement1;
complement2(item) = yes; complement2(subitem1) = no; display complement2;

difference1(item) = subitem2(item) - subitem1(item);                  display difference1;
difference2(item) = yes$(subitem2(item)); difference2(subitem1) = no; display difference2;

The display statements will show that the above assignment statements for each operation result in the same dynamic set like using the set operator. Observe that the alternative formulations for the set intersection and set difference involve conditional assignments. Conditional assignments in the context of dynamic sets are discussed in depth in the next section.

Note
The indexed operation sum may be used for set unions. Similarly, the indexed operation prod may be used for set intersections. For examples see section Conditional Indexed Operations with Dynamic Sets below.

Using Dollar Controls with Dynamic Sets

The remainder of this chapter assumes familiarity with the dollar condition that is introduced in chapter Conditional Expressions, Assignments and Equations. All the dollar control machinery is available for use with dynamic sets. In fact, the full power of dynamic sets can be exploited using these dollar controls.

Recall that set membership of subsets and dynamic sets may be used as a logical condition; see subsection Logical Conditions: Set Membership and Set Functions for details. Set membership may also be a building block in complex logical conditions that are constructed using the logical operators not, and, or, xor, imp and eqv. Moreover, the set operations introduced in the previous section may also be used in logical conditions. Like other dollar conditions, dollar conditions with dynamic sets are used in the context of assignments, indexed operations and equations. We will discuss in detail each of these in the following subsections.

Apart from being part of logical conditions, dynamic sets may be assigned members with conditional assignments. Examples are given in the next subsection.

Dynamic Sets in Conditional Assignments

Dynamic sets may be used in two ways in conditional assignments: they may be the item on the left-hand side that is assigned to and they may be part of the logical condition. Below we present examples for both. The examples are again based on the database model [ZLOOF] that we introduced above.

Set  item            "all items"              / dish, ink, lipstick, pen, pencil, perfume /
     subitem1(item)  "first subset of item"   /       ink, lipstick, pen, pencil          /
     subitem2(item)  "second subset of item";

subitem2(item)$subitem1(item) = yes;
display subitem2; 

The conditional assignment adds the members of dynamic set subitem1 to the dynamic set subitem2. Thus subitem2 will have the following elements:

----      6 SET subitem2  second subset of item

ink     ,    lipstick,    pen     ,    pencil 

Note that instead of using subitem1 in a dollar condition we could also write:

subitem2(subitem1) = yes; 

In the next example of a conditional assignment, a dynamic set features in the logical condition on the right-hand side. The first statement clears the set subitem2 of any previously assigned members and the second statement assigns all members of subitem1 to subitem2. The following conditional assignment will have the same result:

subitem2(item) = no;
subitem2(item) = yes$subitem1(item);

The logical condition in this assignment is subitem1(item). It is satisfied for all members of the set subitem1. Hence the statement assigns all elements of the domain item that are members of the set subitem1 to the dynamic set subitem2. Note that in this assignment the dollar operator is on the right. In the section Dollar on the Right we show that conditional assignments with the dollar operator on the right-hand side imply an if-then-else structure where the else case is automatically zero. Unlike parameters, dynamic sets cannot be assigned the value of zero, they are assigned the value no instead. Therefore a more explicit formulation of the conditional assignment above would be:

subitem2(item) = no;
subitem2(item) = yes$subitem1(item) + no$(not subitem1(item));

For more on sets in logical conditions, see section Logical Conditions: Set Membership and Set Functions. For more on conditional assignments, see section Conditional Assignments.

Conditional Indexed Operations with Dynamic Sets

Indexed operations in GAMS are introduced in section Indexed Operations. They may be controlled by dollar conditions as discussed in section Conditional Indexed Operations. The domain of conditional indexed operations is often restricted by a set, called the conditional set. Dynamic sets may be used as conditional sets or they may be assigned to with a statement that features a conditional indexed operation on the right-hand side. We will illustrate both cases with examples.

Suppose we have a set of origins, a set of destinations and a table specifying the flight distance between them:

Set   i           "origins"       / Chicago, Philadelphia /
      j           "destinations"  / Vancouver, Bogota, Dublin, Rio, Marrakech / ;

Table d(i,j)      "distance (miles)"
                  Vancouver   Bogota   Dublin    Rio    Marrakech
    Chicago          1777      2691     3709     5202      4352
    Philadelphia     2438      2419     3306     4695      3757          ;

We wish to find the longest distance that we can travel given that we have a limit of 3500 miles.

Set   can_do(i,j) "connections with less than 3500 miles";
can_do(i,j)$(d(i,j) < 3500) = yes;
display can_do;
Scalar maxd  "longest distance possible"
maxd = smax((i,j)$can_do(i,j), d(i,j));
display maxd;

The dynamic set can_do contains all connections that are less than 3500 miles. The scalar maxd is defined by a conditional assignment where the indexed operation smax scans all entries of the parameter d whose label combinations are members of the set can_do and chooses the largest value. The output generated by the display statements is shown below:

----     11 SET can_do  connections with less than 3500 miles

               Vancouver      Bogota      Dublin

Chicago              YES         YES
Philadelphia         YES         YES         YES


----     15 PARAMETER maxd                 =     3306.000  longest distance possible

There is a shorter alternative formulation for this assignment; see subsection Filtering through Dynamic Sets below for details.

Finally, we also wish to know which flight connection is linked to the longest possible distance. Consider the following two lines:

Singleton set maxc(i,j)  "maximum distance connection";
maxc(i,j) = yes$can_do(i,j) and (d(i,j) = maxd);

The dynamic singleton set is assigned the member of the dynamic set can_do whose distance equals the maximum distance.

The full power of indexed operators becomes apparent with multi-dimensional dynamic sets. As earlier in this chapter, we illustrate with fragments of code adapted from the relational database model [ZLOOF].

Set  dep         "departments"  / cosmetics, hardware, houshold, stationary, toy /
     sup         "suppliers"    / bic, dupont, parker, revlon /
     item        "items sold"   / dish, ink, lipstick, pen, pencil, perfume /

sales(dep,item)  "departments and items sold"  /
                 cosmetics.  (lipstick,perfume)
                 hardware.    ink
                 houshold.   (dish,pen)
                 stationary. (dish,ink,pen,pencil)
                 toy.        (ink,pen,pencil)         /

supply(item,sup) "items and suppliers"   /
                 dish.(bic,dupont)   , ink.(bic,parker)    , lipstick.revlon
                 pen.(parker,revlon) , pencil.(bic,parker) , perfume.revlon  /

Set g03(dep)    "departments selling items supplied by Parker";

g03(dep) = sum(item$supply(item,'parker'), sales(dep,item));
display g03;

The assignment above is used to create the set of departments that sell items supplied by 'parker'. Note that the set g03 is a subset of the set dep. Its members are specified by assignment, hence it is a dynamic set. Note that the assignment is made to a set, therefore the indexed operator sum refers to a set union (and not to an addition as would be the case if the assignment were made to a parameter). The indexed operation is controlled by the two-dimensional set supply with the label 'parker' in the second index position. This logical condition is TRUE for all members of the set supply where the second index is 'parker'. Hence the summation is over all items sold, provided that the supplier is 'parker'. Given the declaration of the set supply, this means 'ink', 'pen' and 'pencil'. The associated departments are thus all departments except for 'cosmetics':

----     19 SET g03  departments selling items supplied by Parker

hardware  ,    houshold  ,    stationary,    toy    

Now suppose we are interested in the departments that are selling only items supplied by 'parker'. We introduce a new dynamic set g11 and the following assignment adds the desired departments:

Set g11(dep) "departments only selling items supplied by parker";
g11(dep) = prod(sales(dep,item), supply(item,"parker"));
display g11;

Note that the indexed operation prod refers to set intersections in the context of assignments to dynamic sets. From all departments linked with items only those are included where all items sold are supplied by 'parker'. This means that departments that additionally sell items that are not supplied by 'parker' are excluded. Hence, only 'hardware' and 'toy' are added to g11.

Conditional Equations with Dynamic Sets

Recall that dollar conditions in the context of equations may restrict the domain of the equation and they may also feature in the algebraic formulation of the equation; see section Conditional Equations for more information. In both instances dynamic sets may be used as part of the logical condition. Dollar conditions with dynamic sets in the algebra of equations are similar to conditional assignments with dynamic sets; see section Dynamic Sets in Conditional Assignments above. The example that follows illustrates the use of a dynamic set to restrict the domain of definition of an equation. In section Equations Defined over the Domain of Dynamic Sets above we had the following equation definition:

prodbal1(r)..            activity2(r)*price    =e= revenue(r)    ;

Recall that r is a dynamic set and a subset of the set allr. Hence this equation may be rewritten in the following way:

prodbal1(allr)$r(allr).. activity2(allr)*price =e= revenue(allr) ;

Note that both formulations achieve the same result: restricting the domain of definition to those elements that belong to the dynamic set r. While in the second formulation the condition is specified explicitly, in the first formulation the domain is filtered through the dynamic set r. This is the topic of the next subsection.

Filtering through Dynamic Sets

The filtering process is introduced and explained in section Filtering Sets in chapter Conditional Expressions, Assignments and Equations. In certain circumstances it is an alternative to the dollar condition to restrict the domain of equations, sets, variables, parameters and indexed operations. We already saw an example for restricting the domain of definition of an equation in the previous subsection. The next example refers to restricting the domain in an indexed operation. In section Conditional Indexed Operations with Dynamic Sets we had the following assignment:

maxd = smax((i,j)$can_do(i,j), d(i,j));

Recall that maxd is a scalar, i and j are sets, can_do is a dynamic set and d is a two-dimensional parameter. Note that the conditional set is the dynamic set can_do. The assignment may be rewritten in the following way:

maxd = smax(can_do(i,j), d(i,j));

Here the indexed operation is filtered through the dynamic set can_do, a dollar condition is not necessary.