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, 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)

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 then break; end-if
     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.