Set Expressions

Introduction

A set expression is an expression that when evaluated results in a set. It is a non-explicit way of defining a set, which contrasts with the explicit definition that we make when we assign values to a set in a data section, listing them one by one.

The difference between defining a set explicitly and implicitly is exemplified below. Both statements result in the same set, but the first is an assignment statement that explicitly lists all values of the set, while the second is a declaration statement that defines the set using a set of numbers constructor ...

set S = 1 2 3 4 5 6 7 8 ; set S = 1..8 ;
NOTE: Although the statements above define the same set, they cannot be used interchangeably throughout an AMPL program. The first is an assignment statement, and can only occur in a data section, and the second is a declaration statement, and can only occur outside a data section (see Statement Types).

Set expressions can appear in a variety of different contexts in an AMPL program. The above declaration statement is just an example of one place in which they may occur. Set expressions are the basic components of indexing expressions, and we use indexing expressions for many different purposes.

A set expression can be as simple as the name of a single set, S, and an empty set is represented by empty brackets {}. More complex set expressions combine one or multiple of the operators and constructors shown below to produce a set.

Set Theory Operators

We can use the standard operators of set theory to define sets.

SET OPERATION AMPL SET EXPRESSION
Union — A B
Set of all items that are a member of A, or B, or both.
A union B
Intersection — A B
Set of all items that are members of both A and B.
A inter B
Difference — A \ B
Set of all items in A that are not in B.
A diff B
Cartesian (or cross) product — A × B
Set whose members are all possible ordered pairs (a, b), where a is a member of A and b is a member of B.
A cross B
Symmetric Difference — A B
Set of all items which are in A or B, but not in both.
A symdiff B

The union and inter operators, aside from the binary form above, also have an alternative indexed form:

union {i in I} S[i]

The resulting set of the above expression is the union of all sets in the set collection S.

Set of Numbers

1 .. M by 2

The .. operator is used to define a set of numbers. The value on the left of the .. operator is the first value of the set, which in the example is 1. The next value in the set will be 1 plus the gap between consecutive values: 1 + 2 = 3. And so on, up to the maximum value.

The value on the right of the .. operator is the maximum value (M), which may or may not be included in the set. It is only included if M - gap is also included. The by gap part of the expression may be ommited, in which case the AMPL processor assumes a gap between consecutive values of 1.

Set Constructor

setof {i in 1..4} ("Week" & i)

The setof operator is a set constructor operator. We use this operator when we want to define a set whose members are obtained by iterating over the tuples of an indexing expression. In the example above, we iterate over the set of numbers 1 to 4. For each number, we define a set member that is a string that concatenates "Week" and the given number, resulting in the set "Week1" "Week2" "Week3" "Week4".

We can also construct multidimensional sets with the setof operator. To do so, we use a comma separated list of expressions to specify a tuple. A tuple can be a pair, a triplet, a quartet, and so on. For instance, suppose that we have a set NotebookModels, where each model can have 4, 8 or 16 GB of RAM. So we want to construct a set of the possible model-memory pairs, which can be done like this: setof {model in NotebookModels, m in 2..4} (model, m^2).

Indexing Expressions and Iterators

{ a in Cities, b in Cities : a != b }

Indexing expressions alone can also be used as set constructors. The resulting set of an indexing expression is a set with all the possible tuples that satisfy the condition in the expression. The dimension of the resulting set is the number of set expressions in the indexing expression, which are separated by commas. The above example produces a 2 dimensional set with all the possible pairs of different cities.

Any set expression in an indexing expression can be preceded by an iterator of the resulting set. An iterator is basically an object that represents any and all members of a set:

a in Cities

There are two main occasions when we want to use iterators. First, when we want to filter out the tuples of an indexing expression according to a logical condition. Second, when subsequent expressions in the same scope of a given set expression will need to refer to the members of the resulting set of that expression.

We have used iterators to filter the tuples of the indexing expression in the previous section: {a in Cities, b in Cities: a != b}. We wanted the resulting set to contain only pairs of different cities. In order to do so, we have defined an iterator a that represents the members of set Cities that go in the first position of any resulting pair, and an iterator b that represents the members of set Cities that go in the second position of any resulting pair. We filter out the pairs where a equals b by by imposing the condition a != b in the "such that" part of the expression.

We have used iterators to refer to the members of a set in the set constructor example: setof{i in 1..4} ("Week" & i) We wanted to construct a set where each member was obtained from the modification of a member of the 1..4 set. Since we needed to refer to the members of that set in the expression that defined the members of the new set, we have defined an iterator i and used it to produce the resulting values.