Sets, lists, and records



The Mosel language defines the structured types set, array, list, and record. So far we have worked with arrays and sets relying on an intuitive understanding of what is an `array' or a `set'. More formally, we may define an array as a collection of labeled objects of a given type where the label of an array entry is defined by its index tuple.

A set collects objects of the same type without establishing an order among them (as opposed to arrays and lists). Set elements are unique: if the same element is added twice the set still only contains it once.

A list groups objects of the same type. Unlike sets, a list may contain the same element several times. The order of the list elements is specified by construction.

Mosel arrays, sets and lists may be defined for any type, that is the elementary types (including the basic types integer, real, string, boolean and the MP types mpvar and linctr), structured types (array, set, list, record), and external types (contributed to the language by a module).

A record is a finite collection of objects of any type. Each component of a record is called a field and is characterized by its name and its type.

This chapter first presents in a more systematic way the different possibilities of how sets may be initialized (all of which the reader has already encountered in the examples in the first part), and also shows more advanced ways of working with sets. We then introduce lists, showing how to initialize and access them, and finally give some examples of the use of records.

Initializing sets

In the revised formulation of the burglar problem in Chapter Some illustrative examples and also in the models in Chapter More advanced modeling features we have already seen different examples for the use of index sets. We recall here the relevant parts of the respective models.

Constant sets

In the Burglar example the index set is assigned directly in the model:

 declarations
  ITEMS={"camera", "necklace", "vase", "picture", "tv", "video",
         "chest", "brick"}
 end-declarations

Since in this example the set contents is set in the declarations section, the index set ITEMS is a constant set (its contents cannot be changed). To declare it as a dynamic set, the contents needs to be assigned after its declaration:

 declarations
  ITEMS: set of string
 end-declarations

 ITEMS:={"camera", "necklace", "vase", "picture", "tv", "video",
         "chest", "brick"}

Set initialization from file, finalized and fixed sets

In Chapter Integer Programming the reader has encountered several examples how the contents of sets may be initialized from data files.

The contents of the set may be read in directly as in the following case:

 declarations
  WHICH: set of integer
 end-declarations

 initilizations from 'idata.dat'
  WHICH
 end-initializations  

Where idata.dat contains data in the following format:

WHICH: [1 4 7 11 14]

Unless a set is constant, arrays that are indexed by this set are created as dynamic arrays. Since in many cases the contents of a set does not change any more after its initialization, Mosel provides the finalize statement that turns a (dynamic) set into a constant set. Consider the continuation of the example above:

 finalize(WHICH)

 declarations
  x: array(WHICH) of mpvar
 end-declarations

The array of variables x will be created as a static array, without the finalize statement it would be dynamic since the index set WHICH may still be subject to changes. Declaring arrays in the form of static arrays is preferable if the indexing set is known before because this allows Mosel to handle them in a more efficient way.

Index sets may also be initialized indirectly during the initialization of dynamic arrays:

 declarations
  REGION: set of string
  DEMAND: array(REGION) of real
 end-declarations

 initializations from 'transprt.dat'
  DEMAND
 end-initilizations  

If file transprt.dat contains the data:

DEMAND: [(Scotland) 2840 (North) 2800 (West) 2600 (SEast) 2820 (Midlands) 2750]

then printing the set REGION after the initialization will give the following output:

{`Scotland',`North',`West',`SEast',`Midlands'}

Once a set is used for indexing an array (of data, decision variables etc.) it is fixed, that is, its elements can no longer be removed, but it may still grow in size.

The indirect initialization of (index) sets is not restricted to the case that data is input from file. In the following example (model chess3.mos) we add an array of variable descriptions to the chess problem introduced in Chapter Getting started with Mosel. These descriptions may, for instance, be used for generating a nice output. Since the array DescrV and its indexing set Allvars are dynamic they grow with each new variable description that is added to DescrV.

model "Chess 3"
 uses "mmxprs"

 declarations
  Allvars: set of mpvar
  DescrV: array(Allvars) of string
  small, large: mpvar
 end-declarations

 DescrV(small):= "Number of small chess sets"
 DescrV(large):= "Number of large chess sets"
 
 Profit:=  5*small + 20*large
 Lathe:=   3*small + 2*large <= 160
 Boxwood:=   small + 3*large <= 200
  
 maximize(Profit)

 writeln("Solution:\n Objective: ", getobjval)
 writeln(DescrV(small), ": ", getsol(small))
 writeln(DescrV(large), ": ", getsol(large))

end-model

The reader may have already remarked another feature that is illustrated by this example: the indexing set Allvars is of type mpvar. So far only basic types have occurred as index set types but as mentioned earlier, sets in Mosel may be of any elementary type, including the MP types mpvar and linctr.

Working with sets

In all examples of sets given so far sets are used for indexing other modeling objects. But they may also be used for different purposes.

The following example (model setops.mos) demonstrates the use of basic set operations in Mosel: union (+), intersection (*), and difference (-):

model "Set example" 

 declarations 
  Cities={"rome", "bristol", "london", "paris", "liverpool"}
  Ports={"plymouth", "bristol", "glasgow", "london", "calais", 
              "liverpool"}
  Capitals={"rome", "london", "paris", "madrid", "berlin"}
 end-declarations

 Places:= Cities+Ports+Capitals        ! Create the union of all 3 sets 
 In_all_three:= Cities*Ports*Capitals  ! Create the intersection of all 3 sets 
 Cities_not_cap:= Cities-Capitals      ! Create the set of all cities that are
                                       ! not capitals

 writeln("Union of all places: ", Places)
 writeln("Intersection of all three: ", In_all_three)
 writeln("Cities that are not capitals: ", Cities_not_cap)

end-model

The output of this example will look as follows:

  Union of all places:{`rome',`bristol',`london',`paris',`liverpool',
  `plymouth',`bristol',`glasgow',`calais',`liverpool',`rome',`paris',
  `madrid',`berlin'}
  Intersection of all three: {`london'}
  Cities that are not capitals: {`bristol',`liverpool}

Sets in Mosel are indeed a powerful facility for programming as in the following example (model prime.mos) that calculates all prime numbers between 2 and some given limit.

Starting with the smallest one, the algorithm takes every element of a set of numbers SNumbers (positive numbers between 2 and some upper limit that may be specified when running the model), adds it to the set of prime numbers SPrime and removes the number and all its multiples from the set SNumbers.

model Prime

 parameters
  LIMIT=100                     ! Search for prime numbers in 2..LIMIT
 end-parameters

 declarations
  SNumbers: set of integer      ! Set of numbers to be checked
  SPrime: set of integer        ! Set of prime numbers
 end-declarations

 SNumbers:={2..LIMIT} 
 
 writeln("Prime numbers between 2 and ", LIMIT, ":")

 n:=2
 repeat
   while (not(n in SNumbers)) n+=1
   SPrime += {n}                ! n is a prime number
   i:=n
   while (i<=LIMIT) do          ! Remove n and all its multiples
     SNumbers-= {i}
     i+=n
   end-do
 until SNumbers={}    

 writeln(SPrime)
 writeln(" (", getsize(SPrime), " prime numbers.)")
 
end-model

This example uses a new function, getsize, that if applied to a set returns the number of elements of the set. The condition in the while loop is the logical negation of an expression, marked with not: the loop is repeated as long as the condition n in SNumbers is not satisfied.

Set operators

The preceding example introduces the operator += to add sets to a set (there is also an operator -= to remove subsets from a set). Another set operator used in the example is in denoting that a single object is contained in a set. We have already encountered this operator in the enumeration of indices for the forall loop.

Mosel also defines the standard operators for comparing sets: subset (<=), superset (>=), difference (<>), end equality (=). Their use is illustrated by the following example (model setcomp.mos):

model "Set comparisons"

 declarations
  RAINBOW = {"red", "orange", "yellow", "green", "blue", "purple"}
  BRIGHT = {"yellow", "orange"}
  DARK = {"blue", "brown", "black"}
 end-declarations

 writeln("BRIGHT is included in RAINBOW: ", BRIGHT <= RAINBOW) 
 writeln("RAINBOW is a superset of DARK: ", RAINBOW >= DARK)
 writeln("BRIGHT is different from DARK: ", BRIGHT <> DARK)
 writeln("BRIGHT is the same as RAINBOW: ", BRIGHT = RAINBOW)

end-model

As one might have expected, this example produces the following output:

BRIGHT is included in RAINBOW: true 
RAINBOW is a superset of DARK: false
BRIGHT is different from DARK: true
BRIGHT is the same as RAINBOW: false

Initializing lists

Lists are not commonly used in the standard formulation of Mathematical Programming problems. However, this data structure may be useful for the Mosel implementation of some more advanced solving and programming tasks.

Constant list

If the contents of a list are specified at the declaration of the list, such as

 declarations
  L = [1,2,3,4,5,6,7,8,9,10]
 end-declarations

we have defined a constant list (its contents cannot be changed). If we want to be able to modify the list contents subsequently we need to separate the definition of the list contents from the declaration, resulting in a dynamic list:

 declarations
  L: list of integer
 end-declarations
 
 L:= [1,2,3,4,5,6,7,8,9,10] 

A two-dimensional array of lists may be defined thus (and higher dimensional arrays by analogy):

 declarations
  M: array(range,set of integer) of list of string
 end-declarations
 
 M:: (2..4,1)[['A','B','C'], ['D','E'], ['F','G','H','I']] 

List initialization from file

Similarly to what we have already seen for other data structures, the contents of lists may be initialized from file through initializations blocks. For example,

 declarations
  K: list of integer
  N: array(range,set of integer) of list of string
 end-declarations
 
 initializations from "listinit.dat"
  K  N
 end-initializations

 writeln("K: ", K)
 writeln("An entry of N: ", N(5,3)) 

Assuming the datafile listinit.dat contains these lines

K: [5,4,3,2,1,1,2,3,4,5]

N: [(3) ['B','C','A']
    (5) ['K','L']
    (5) ['D','E']
    (6) ['H','I','F','G']] 

we obtain the following output from the model fragment above:

K: [5,4,3,2,1,1,2,3,4,5]
An entry of N: [`K',`L',`D',`E']  

Working with lists

Enumeration

Similarly to the way we have used sets so far, lists may be used as loop indices for enumeration. The following enumerates a given list L from beginning to end:

 declarations
  L: list of integer
 end-declarations
 
 L:= [1,2,3,4,5] 

 forall(i in L) writeln(i) 

Since lists have an ordering we may choose, for instance, to reverse the order of list elements for the enumeration. The model listenum.mos below shows several possibilities for enumerating lists in inverse order: (1) reversing a copy of the list to enumerate, (2) reversing the list to enumerate. In the first case we obtain the reversed copy of the list with function getreverse, in the second case we modify the original list by applying to it the procedure reverse.

model "Reversing lists"

 declarations
  K,L: list of integer
 end-declarations
 
 L:= [1,2,3,4,5] 

! Enumeration in inverse order:
 ! 1. Reversed copy of the list (i.e., no change to 'L')
 K:=getreverse(L)
 forall(i in K) writeln(i)

 ! 2. Reversing the list itself
 reverse(L)
 forall(i in L) writeln(i) 

end-model 

List operators

Lists are composed by concatenating several lists or by truncating their extremities (refered to as head and tail). The operators += and + serve for concatenating lists. Their inverses (-= and -) may be used to remove the tail of a list—they will not remove the given sublist if it is not positioned at the end.

The following model listops.mos shows some examples of the use of list operators. Besides the concatenation operators + and += we also use the aggregate form sum. Another list operator used in this example is the comparison operator <> (the comparison operator = may also be used with lists).

model "List operators"

 declarations
  L,M: list of integer
 end-declarations
 
 L:= [1,2,3] + [4,5]; writeln("L (1): ", L) 
 L+= [6,7,8]; writeln("L (2): ", L) 
 L-= [1,2,3]; writeln("L (3): ", L) 

 M:= sum(l in L) [l*2]; writeln("M: ", M)
 
 writeln("L and M are different: ", L<>M)

end-model 

As can be seen in the output, the list [1,2,3] is not removed from L since it is not located at its tail:

L (1): [1,2,3,4,5]
L (2): [1,2,3,4,5,6,7,8]
L (3): [1,2,3,4,5,6,7,8]
M: [2,4,6,8,10,12,14,16]
L and M are different: true 

List handling functions

The Mosel subroutines for list handling form two groups, namely

The following example listmerge.mos merges two lists of integers K and L, the elements of which are ordered in increasing order of their values into a new list M that is ordered in the same way. The elements of the two original lists are added one-by-one to the new list using the concatenation operator +=. Whilst the elements of the list K are simply enumerated, we iteratively split off the first element from list L (using splithead with second argument 1 to take away just the first list element) so that this list will be empty at the end of the forall loop. If this is not desired, we need to work with a copy of this list.

model "Merging lists"

 declarations
  K,L,M: list of integer
 end-declarations
 
 K:= [1,4,5,8,9,10,13]
 L:= [-1,0,4,6,7,8,9,9,11,11] 

 forall(k in K) do
  while (L<>[] and k >= getfirst(L))  M += splithead(L,1)
  M+= [k]
 end-do  
 
 writeln(M)

end-model 

The resulting list M is:

[-1,0,1,4,4,5,6,7,8,8,9,9,9,10,11,11,13] 

List handling routines provide a powerful means of programming, illustrated by the following example euler.mos that constructs a Eulerian circuit for the network shown in Figure Network forming a Eulerian circuit (thick arrows indicate that the corresponding arc is to be used twice). This example is an alternative implementation of the Eulerian circuit algorithm described in Section 15.4 `Gritting roads' (problem j4grit) of the book 'Applications of optimization with Xpress-MP'.

MoselUG/j4grit2b

Figure 10.1: Network forming a Eulerian circuit

A Eulerian circuit is a tour through a network that uses every given arc exactly once. To construct such a circuit for a given set of arcs we may employ the following algorithm

model "Eulerian circuit"

 declarations
  NODES = 1..12                        ! Set of nodes
  UNUSED: array(NODES) of list of integer
  TOUR: list of integer
  NEWT, TAIL: list of integer
 end-declarations

 initializations from 'euler.dat'
  UNUSED
 end-initializations
 
 ct:=sum(i in NODES) getsize(UNUSED(i))

 TOUR:=[1]                            ! Choose node 1 as start point

 while(ct>0) do                       ! While there are unused arcs:
     ! Find first node in TOUR with unused outgoing arc(s) 
  node:=0
  forall(i in TOUR)
   if UNUSED(i) <> [] then
    node:=i
    break
   end-if

     ! Insertion position (first occurrence of 'node' in TOUR)  
  pos:= findfirst(TOUR, node) 

     ! Construct a new subtour starting from 'node'
  cur:=node                           ! Start with current node
  NEWT:=[]
  while(UNUSED(cur) <> []) do
   NEWT+=splithead(UNUSED(cur),1)     ! Take first unused arc
   cur:=getlast(NEWT)                 ! End point of arc is new current node
  end-do
  
     ! Stop if the subtour is not a closed loop (=> no Eulerian circuit)
  if cur<>node then                   ! Compare start and end of subtour
   writeln("Tour cannot be closed")
   exit(1)
  end-if 

     ! Add the new subtour to the main journey 
  TAIL:=splittail(TOUR, -pos)         ! Split off the tail from main tour
  TOUR += NEWT + TAIL                 ! Attach subtour and tail to main tour
  ct -= getsize(NEWT)
 end-do
 
 writeln("Tour: ", TOUR)              ! Print the result
 
end-model 

The data file euler.dat corresponding to the graph in Figure Network forming a Eulerian circuit has the following contents:

UNUSED: [(1) [2 5] (2) [3 5 6] (3) [2 4 4] (4) [3 8 8] 
         (5) [1 1 6 6] (6) [2 5 7 9 9 10] (7) [3 6 8 11] 
         (8) [4 11 12] (9) [5 10] (10) [6 6 7] 
         (11) [7 7 10] (12) [11] ] 

A Eulerian circuit for this data set is the tour

1 Maths/rightarrow.png 2 Maths/rightarrow.png 6 Maths/rightarrow.png 5 Maths/rightarrow.png 6 Maths/rightarrow.png 7 Maths/rightarrow.png 8 Maths/rightarrow.png 12 Maths/rightarrow.png 11 Maths/rightarrow.png 7 Maths/rightarrow.png 11 Maths/rightarrow.png 10 Maths/rightarrow.png 7 Maths/rightarrow.png 3 Maths/rightarrow.png 4 Maths/rightarrow.png 3 Maths/rightarrow.png 4 Maths/rightarrow.png 8 Maths/rightarrow.png 4 Maths/rightarrow.png 8 Maths/rightarrow.png 11 Maths/rightarrow.png 7 Maths/rightarrow.png 6 Maths/rightarrow.png 9 Maths/rightarrow.png 5 Maths/rightarrow.png 6 Maths/rightarrow.png 9 Maths/rightarrow.png 10 Maths/rightarrow.png 6 Maths/rightarrow.png 10 Maths/rightarrow.png 6 Maths/rightarrow.png 2 Maths/rightarrow.png 3 Maths/rightarrow.png 2 Maths/rightarrow.png 5 Maths/rightarrow.png 1 Maths/rightarrow.png 5 Maths/rightarrow.png 1

Records

Records group Mosel objects of different types. They may be used, for instance, to structure the data of a large-scale model by collecting all information relating to the same object.

Defining records

The definition of a record has some similarities with the declarations block: it starts with the keyword record, followed by a list of field names and types, and the keyword end-record marks the end of the definition. The definition of records must be placed in a declarations block. The following code extract defines a record with two fields (`name' and `values').

 declarations 
  R = 1..10
  D: record
   name: string
   values: array(R) of real
  end-record
 end-declarations

We need to define a name (e.g., `mydata') for the record if we want to be able to refer to it elsewhere in the model. For example:

 declarations 
  R = 1..10
  mydata = record
   name: string
   values: array(R) of real
  end-record
  D: mydata
  A: array(range) of mydata
 end-declarations

The fields of a record are accessed by appending .fieldname to the record, for instance:

 D.name:= "D"
 forall(i in R) D.values(i):= i
 writeln("Values of ", D.name, ": ", D.values)
 
 writeln("An entry of A: ", A(1))
 writeln("'name' of an entry of A: ", A(4).name)
 writeln("'values' of an entry of A: ", A(3).values)
 writeln("First entry of 'values': ", A(3).values(1)) 

Note: if a record field is an array, the index set(s) of the array must be either constant or be declared outside of the record definition. So, these are valid record definitions:

 declarations 
  R: range
  P: record
   values: array(R) of real
  end-record

  Q: record
   values: array(1..10) of real
  end-record
 end-declarations

whereas this form can not be used:

  Q: record
   values: array(range) of real
  end-record 

Initialization of records from file

The contents of a record may be assigned fieldwise within a model as shown above or else be read in from file using initializations. The data file must contain the data entries for the different record fields in their order of occurrence in the record definition. An array A of the record type mydata defined in the previous section is initialized with data from file in the obvious way (model recorddef.mos):

 declarations 
  A: array(T:range) of mydata
 end-declarations
 
 initializations from "recorddef.dat"
  A
 end-initializations

 writeln(A(1))
 forall(i in T | exists(A(i))) writeln(A(i).name) 

If the data file recorddef.dat has these contents:

A: [(1) ['A1' [(2) 2 (3) 3 (4) 4] ] 
    (3) ['A3' [(3) 6 (6) 9] ]
    (4) ['A4' [5 6 7 8] ]
   ]  

we obtain the following output:

 [name=`A1' values=[0,2,3,4,0,0,0,0,0,0]]
A1
A3
A4  

An example of the use of records is the encoding of arcs and associated information such as for representing the network in Figure Network with costs on arcs.

MoselUG/arcs

Figure 10.2: Network with costs on arcs

A data file with the network data may look as follows (file arcs.dat):

ARC: [(1) ["A" "B" 2]
      (2) ["A" "D" 4]
      (3) ["A" "C" 7]
      (4) ["B" "F" 4]
      (5) ["B" "D" 3]
      (6) ["C" "B" 5]
      (7) ["C" "D" 1]
      (8) ["C" "E" 1]
      (9) ["D" "F" 2]
     (10) ["D" "E" 5]
     (11) ["E" "F" 8] ]  

We may then write our model arcs.mos thus

model "Arcs"

 declarations
  NODES: set of string                  ! Set of nodes
  ARC: array(ARCSET:range) of record    ! Arcs:
   Source,Sink: string                  !   Source and sink of arc
   Cost: real                           !   Cost coefficient
  end-record 
 end-declarations

 initializations from 'arcs.dat'
  ARC
 end-initializations

! Calculate the set of nodes
 NODES:=union(a in ARCSET) {ARC(a).Source, ARC(a).Sink}
 writeln(NODES)

 writeln("Average arc cost: ", sum(a in ARCSET) ARC(a).Cost / getsize(ARCSET) )

end-model 

User types

In a Mosel model, the user may define new types that will be treated in the same way as the predefined types of the Mosel language. New types are defined in declarations blocks by specifying a type name, followed by =, and the definition of the type. The simplest form of a type definition is to introduce a new name for an existing type, such as:

declarations
  myint = integer
  myreal = real
 end-declarations 

In the section on records above we have already seen an example of a user type definition for records (where we have named the record `mydata'). Another possible use of a user type is as a kind of `shorthand' where several (data) arrays have the same structure, such as in the model blend.mos from Chapter Some illustrative examples, where, instead of

 declarations
  ORES = 1..2                    ! Range of ores

  COST: array(ORES) of real      ! Unit cost of ores
  AVAIL: array(ORES) of real     ! Availability of ores
  GRADE: array(ORES) of real     ! Grade of ores (measured per unit of mass)
 end-declarations 

we could have written

 declarations
  ORES = 1..2                    ! Range of ores

  myarray = array(ORES) of real  ! Define a user type

  COST: myarray                  ! Unit cost of ores
  AVAIL: myarray                 ! Availability of ores
  GRADE: myarray                 ! Grade of ores (measured per unit of mass)
 end-declarations 

without making any other modifications to the model.



If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.