Flow control constructs
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-then statement:
- if-then: `If a condition holds do something'. For example:
if A >= 20 then x <= 7 end-ifFor 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 there may be any number of expressions between then and end-if, not just a single one.
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-ifHere 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-ifHere 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-caseHere 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-modelInstead 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, 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_binaryThe 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-modelThe 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_binaryConditional 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-ifIf 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)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-modelrepeat 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, inck+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-modelThe 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.
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.