Flow control constructs

Topics covered in this chapter:

Flow control constructs are mechanisms for controlling the order of the execution of the actions in a program. In this chapter we are going to have a closer look at two fundamental types of control constructs in Mosel: selections and loops.

Frequently actions in a program need to be repeated a certain number of times, for instance for all possible values of some index or depending on whether a condition is fulfilled or not. This is the purpose of loops. Since in practical applications loops are often interwoven with conditions (selection statements), these are introduced first.

Selections

Mosel provides several statements to express a selection between different actions to be taken in a program. The simplest form of a selection is the if statement:

• if: `If a condition holds do something'. For example:

    if A >= 20: x <= 7

  For an integer number A and a variable x of type mpvar, x is constrained to be less or equal to 7 if A is greater or equal 20.

Note that the if statement can only be followed by a single expression. With the if-then statement there may be any number of expressions between then and end-if, not just a single one:

• if-then: `If a condition holds do something' (possibly several actions).

    if A >= 20 then
      x <= 7
    end-if

In other cases, it may be necessary to express choices with alternatives.

• if-then-else: `If a condition holds, do this, otherwise do something else'. For example:

    if A >= 20 then
      x <= 7
    else x >= 35
    end-if

  Here the upper bound 7 is applied to the variable x if the value of A is greater or equal 20, otherwise the lower bound 35 is applied to it.
• if-then-elif-then-else: `If a condition holds do this, otherwise, if a second condition holds do something else etc.'

    if A >= 20 then
      x <= 7
    elif A <= 10 then
      x >= 35
    else
      x = 0
    end-if

  Here the upper bound 7 is applied to the variable x if the value of A is greater or equal 20, and if the value of A is less or equal 10 then the lower bound 35 is applied to x. In all other cases (that is, A is greater than 10 and smaller than 20), x is fixed to 0.
  Note that this could also be written using two separate if-then statements but it is more efficient to use if-then-elif-then[-else] if the cases that are tested are mutually exclusive.
• case: `Depending on the value of an expression do something'.

    case A of
      -MAX_INT..10 : x >= 35
      20..MAX_INT :  x <= 7
      12, 15 :       x = 1
      else           x = 0
    end-case

  Here the upper bound 7 is applied to the variable x if the value of A is greater or equal 20, and the lower bound 35 is applied if the value of A is less or equal 10. In addition, x is fixed to 1 if A has value 12 or 15, and fixed to 0 for all remaining values.
  An example for the use of the case statement is given in Section Goal Programming.

The following example (model minmax.mos) uses the if-then-elif-then statement to compute the minimum and the maximum of a set of randomly generated numbers:

model Minmax

 declarations
   SNumbers: set of integer
   LB=-1000                    ! Elements of SNumbers must be between LB
   UB=1000                     ! and UB
 end-declarations

! Generate a set of 50 randomly chosen numbers
 forall(i in 1..50)
   SNumbers += {round(random*200)-100}

 writeln("Set: ", SNumbers, " (size: ", getsize(SNumbers), ")")

 minval:=UB
 maxval:=LB
 forall(p in SNumbers)
   if p<minval then
     minval:=p
   elif p>maxval then
     maxval:=p
   end-if

 writeln("Min: ", minval, ", Max: ", maxval)

end-model 

Instead of writing the loop above, it would of course be possible to use the corresponding operators min and max provided by Mosel:

  writeln("Min: ", min(p in SNumbers) p, ", Max: ", max(p in SNumbers) p)

It is good programming practice to indent the block of statements in loops or selections as in the preceding example so that it becomes easy to get an overview where the loop or the selection ends. — At the same time this may serve as a control whether the loop or selection has been terminated correctly (i.e. no end-if or similar key words terminating loops have been left out).

Loops

Loops group actions that need to be repeated a certain number of times, either for all values of some index or counter (forall) or depending on whether a condition is fulfilled or not (while, repeat-until).

This section presents the complete set of loops available in Mosel, namely forall, forall-do, with, while, while-do, and repeat-until.

forall

The forall loop repeats a statement or block of statements for all values of an index or counter. If the set of values is given as an interval of integers (range), the enumeration starts with the smallest value. For any other type of sets the order of enumeration depends on the current (internal) order of the elements in the set.

The forall loop exists in two different versions in Mosel. The inline version of the forall loop (i.e. looping over a single statement) has already been used repeatedly, for example as in the following loop that constrains variables x(i) (i=1,...,10) to be binary.

  forall(i in 1..10) x(i) is_binary

The second version of this loop, forall-do, may enclose a block of statements, the end of which is marked by end-do.

Note that the indices of a forall loop can not be modified inside the loop. Furthermore, they must be new objects: a symbol that has been declared cannot be used as index of a forall loop.

The following example (model perfect.mos) that calculates all perfect numbers between 1 and a given upper limit combines both types of the forall loop. (A number is called perfect if the sum of its divisors is equal to the number itself.)

model Perfect

 parameters
  LIMIT=100
 end-parameters

 writeln("Perfect numbers between 1 and ", LIMIT, ":")

 forall(p in 1..LIMIT) do
   sumd:=1
   forall(d in 2..p-1)
    if p mod d = 0 then          ! Mosel's built-in mod operator
      sumd+=d                    ! The same as sum:= sum + d
     end-if
   if p=sumd then
     writeln(p)
   end-if
 end-do

end-model

The outer loop encloses several statements, we therefore need to use forall-do. The inner loop only applies to a single statement (if statement) so that we may use the inline version forall.

If run with the default parameter settings, this program computes the solution 1, 6, 28.

Multiple indices

The forall statement (just like the sum operator and any other statement in Mosel that requires index set(s)) may take any number of indices, with values in sets of any basic type or ranges of integer values. If two or more indices have the same set of values as in

  forall(i in 1..10, j in 1..10) y(i,j) is_binary

(where y(i,j) are variables of type mpvar) the following equivalent short form may be used:

 forall(i,j in 1..10) y(i,j) is_binary

Conditional looping

The possibility of adding conditions to a forall loop via the `|' symbol has already been mentioned in Chapter More advanced modeling features. Conditions may be applied to one or several indices and the selection statement(s) can be placed accordingly. Take a look at the following example where A and U are one- and two-dimensional arrays of integers or reals respectively, and y a two-dimensional array of decision variables (mpvar):

 forall(i in -10..10, j in 0..5 | A(i) > 20) y(i,j) <= U(i,j)

For all i from -10 to 10, the upper bound U(i,j) is applied to the variable y(i,j) if the value of A(i) is greater than 20.

The same conditional loop may be reformulated (in an equivalent but usually less efficient way) using the if statement:

  forall(i in -10..10, j in 0..5)
   if A(i) > 20
    y(i,j) <= U(i,j)
  end-if

If we have a second selection statement on both indices with B a two-dimensional array of integers or reals, we may either write

 forall(i in -10..10, j in 0..5 | A(i) > 20 and B(i,j) <> 0 ) y(i,j) <= U(i,j)

or, more efficiently, since the second condition on both indices is only tested if the condition on index i holds:

 forall(i in -10..10 | A(i) > 20, j in 0..5 | B(i,j) <> 0 ) y(i,j) <= U(i,j)

Counters

A recurring programming task when working with loops, and in particular with conditional loops, is to determine the number of times that the loop has been executed (or that the loop condition is veryfied). To this aim, Mosel provides the construct as counter, to be added to the indices of forall loops or other statements involving indices, such as sum, max, or union statements.

The following example (see file count1.mos) counts and displays all strings in a list that contain the substring 'b':

 L:= ['a', 'ab', 'abc', 'da', 'bc', 'db']
 scnt:=0
 forall(scnt as counter, s in L | findtext(s, 'b', 1)>0)
   writeln(scnt, ": ", s) 

The position of as counter among the loop indices is entirely up to the programmer and takes no effect on its value. However notice that loop conditions must succeed an index. So for instance, instead of the above we might equally have written:

 forall(s in L | findtext(s, 'b', 1)>0, scnt as counter)
  writeln(scnt, ": ", s) 

And here is an elegant formulation how to calculate the average value of set elements with a given property (odd numbers):

 S:= {1, 5, 8, -1, 4, 7, 2}
 cnt:=0.0
 writeln("Average of odd numbers: ",
         (sum(cnt as counter, i in S | isodd(i)) i) / cnt) 

As an alternative to adding a counter on a loop, Mosel also defines the aggregate operator count that is used as follows.

 writeln("Number of odd numbers in S: ", count(i in S | isodd(i)) )

 writeln("Occurences of 'b' in L: ", count(s in L | findtext(s, 'b', 1)>0) )

Both types of counters may be used jointly in a single statement as shown in the following example (model count2.mos) that creates an entry for the array NODE if there are at least two incoming or outgoing arcs for the corresponding index j.

 declarations
   I: set of integer
   ARC: dynamic array(I,I) of boolean
   NODE: dynamic array(set of integer) of integer
 end-declarations

 initializations from "count2.dat"
   ARC
 end-initializations

 ctnode:=0
 forall(ctnode as counter, j in I |
        count(i in I | exists(ARC(i,j))) +
        count(i in I | exists(ARC(j,i))) >= 2) create(NODE(j))
		
 writeln("Number of nodes created: ", ctnode)

with

The with statement is handled like a single iteration of a forall loop. It allows the developer to work with local declarations for a block of code that needs to be surrounded by do / end-do even if it only contains a single statement. Such local declarations can be used, for example, to simplify and speed up repeated access to specific elements of complex data structures as shown in the code snippet below (file usingwith.mos).

 declarations
   NB: dynamic array(R:range) of set of integer
 end-declarations

 NB(1):={2,3,4}; NB(2):={1,3,5,6}; NB(6):={2,4}
 forall(i in R | exists(NB(i)) )
   with S=NB(i), el=getelt(S) do
     writeln(i, ": Size of set=", S.size, ", contains 1:", 1 in S,
             ", an element of the set:", el, " is different from 0:", el<>0)
   end-do

Note that forall loop statements equally accept local declarations of scalars (but not of structured types). In the example above the declaration of the scalar el could be moved directly into the forall statement, but not the local declaration of the set S:

 forall(i in R | exists(NB(i)), el=getelt(NB(i)))
   with S=NB(i) do
     ...

Local declarations in with statements can also serve for aliasing arrays along with their index set(s), for example when a program needs to enumerate an array that has been declared without naming its indexing sets (note also the use of exists with the locally declared entities in this example):

 declarations
   A1: dynamic array(range,string) of integer  ! Array with unnamed index sets
 end-declarations

 A1(1,'a'):=1; A1(4,'c'):=4; A1(6,'d'):=6

 with A(I,J)=A1 do
   forall(i in I, j in J | exists(A(i,j))) write(" ", A(i,j))
 end-do
 writeln 

while

A while loop is typically employed if the number of times that the loop needs to be executed is not know beforehand but depends on the evaluation of some condition: a set of statements is repeated while a condition holds. As with forall, the while statement exists in two versions, an inline version (while) and a version (while-do) that is to be used with a block of program statements.

The following example (model lcdiv1.mos) computes the largest common divisor of two integer numbers A and B (that is, the largest number by which both A and B, can be divided without remainder). Since there is only a single if-then-else statement in the while loop we could use the inline version of the loop but, for clarity's sake, we have given preference to the while-do version that marks where the loop terminates clearly.

model Lcdiv1

 declarations
   A,B: integer
 end-declarations

 write("Enter two integer numbers:\n  A: ")
 readln(A)
 write("  B: ")
 readln(B)

 while (A <> B) do
   if A>B then
     A:=A-B
   else B:=B-A
   end-if
 end-do

 writeln("Largest common divisor: ", A)

end-model

repeat until

The repeat-until structure is similar to the while statement with the difference that the actions in the loop are executed once before the termination condition is tested for the first time.

The following example (model shsort.mos) combines the three types of loops (forall, while, repeat-until) that are available in Mosel. It implements a Shell sort algorithm for sorting an array of numbers into numerical order. The idea of this algorithm is to first sort, by straight insertion, small groups of numbers. Then several small groups are combined and sorted. This step is repeated until the whole list of numbers is sorted.

The spacings between the numbers of groups sorted on each pass through the data are called the increments. A good choice is the sequence which can be generated by the recurrence inc_1=1, inc_k+1=3·inc_k+1, k=1,2,...

model "Shell sort"

 declarations
   N: integer                   ! Size of array ANum
   ANum: array(range) of real   ! Unsorted array of numbers
 end-declarations

 N:=50
 forall(i in 1..N) ANum(i):=round(random*100)

 writeln("Given list of numbers (size: ", N, "): ")
 forall(i in 1..N) write(ANum(i), " ")
 writeln

 inc:=1                         ! Determine the starting increment
 repeat
   inc:=3*inc+1
 until (inc>N)

 repeat                         ! Loop over the partial sorts
   inc:=inc div 3
   forall(i in inc+1..N) do     ! Outer loop of straight insertion
     v:=ANum(i)
     j:=i
     while (ANum(j-inc)>v) do   ! Inner loop of straight insertion
       ANum(j):=ANum(j-inc)
       j -= inc
       if j<=inc: break
     end-do
     ANum(j):= v
   end-do
 until (inc<=1)

 writeln("Ordered list: ")
 forall(i in 1..N) write(ANum(i), " ")
 writeln

end-model

The example introduces a new statement: break. It can be used to interrupt one or several loops. In our case it stops the inner while loop. Since we are jumping out of a single loop, we could as well write break 1. If we wrote break 3, the break would make the algorithm jump 3 loop levels higher, that is outside of the repeat-until loop.

Note that there is no limit to the number of nested levels of loops and/or selections in Mosel.