[Previous chapter] [Next chapter]

Some illustrative examples

This chapter develops the basics of modeling set out in Chapter Getting started with Mosel. It presents some further examples of the use of Mosel and introduces new features:

Use of subscripts: Almost all models of any size have subscripted variables. We show how to define arrays of data and decision variables, introduce the different types of sets that may be used as index sets for these arrays, and also simple loops over these sets.

Working with data files: Mosel provides facilities to read
from and write to data files in text format and also from other data sources (databases and spreadsheets).

The burglar problem

A burglar sees 8 items, of different worths and weights. He wants to take the items of greatest total value whose total weight is not more than the maximum WTMAX he can carry.

Model formulation

We introduce binary variables take_i for all i in the set of all items (ITEMS) to represent the decision whether item i is taken or not. take_i has the value 1 if item i is taken and 0 otherwise. Furthermore, let VALUE_i be the value of item i and WEIGHT_i its weight. A mathematical formulation of the problem is then given by:

maximize

_{i ITEMS}

VALUE_i · take_i

_{i ITEMS}

WEIGHT_i · take_i WTMAX (weight restriction)
i ITEMS: take_i {0,1}

The objective function is to maximize the total value, that is, the sum of the values of all items taken. The only constraint in this problem is the weight restriction. This problem is an example of a knapsack problem.

Implementation

It may be implemented with Mosel as follows (model file burglar.mos):
model Burglar 
 uses "mmxprs"
  
 declarations
  WTMAX = 102                    ! Maximum weight allowed
  ITEMS = 1..8                   ! Index range for items
  
  VALUE: array(ITEMS) of real    ! Value of items
  WEIGHT: array(ITEMS) of real   ! Weight of items
  
  take: array(ITEMS) of mpvar    ! 1 if we take item i; 0 otherwise
 end-declarations

! Item:      1   2   3   4   5   6   7   8
  VALUE :: [15, 100, 90, 60, 40, 15, 10,  1]
  WEIGHT:: [ 2,  20, 20, 30, 40, 30, 60, 10]

! Objective: maximize total value
 MaxVal:= sum(i in ITEMS) VALUE(i)*take(i) 

! Weight restriction
 sum(i in ITEMS) WEIGHT(i)*take(i) <= WTMAX

! All variables are 0/1
 forall(i in ITEMS) take(i) is_binary  

 maximize(MaxVal)                 ! Solve the MIP-problem

! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 forall(i in ITEMS)  writeln(" take(", i, "): ", getsol(take(i)))
end-model
When running this model we get the following output:
Solution:
 Objective: 280
 take(1): 1
 take(2): 1
 take(3): 1
 take(4): 1
 take(5): 0
 take(6): 1
 take(7): 0
 take(8): 0
In this model there are a lot of new features, which we shall now explain.
Constants:
  WTMAX=102
declares a constant called WTMAX, and gives it the value 102. Since 102 is an integer, WTMAX is an integer constant. Anything that is given a value in a declarations block is a constant.
Ranges:
  ITEMS = 1..8
defines a range set, that is, a set of consecutive integers from 1 to 8. This range is used as an index set for the data arrays (VALUE and WEIGHT) and for the array of decision variables take.
Arrays:
  VALUE: array(ITEMS) of real
defines a one-dimensional array of real values indexed by the range ITEMS. Exactly equivalent would be
  VALUE: array(1..8) of real    ! Value of items
Multi-dimensional arrays are declared in the obvious way e.g.
  VAL3: array(ITEMS, 1..20, ITEMS) of real
declares a 3-dimensional real array. Arrays of decision variables (type mpvar) are declared likewise, as shown in our example:
  x: array(ITEMS) of mpvar
declares an array of decision variables take(1), take(2), ..., take(8).
All objects (scalars and arrays) declared in Mosel are always initialized with a default value:
real, integer: 0
boolean: false
string: '' (i.e. the empty string)
In Mosel, reals are double precision.
Assigning values to arrays: The values of data arrays may either be defined in the model as we show in the example or initialized from file (see Section A blending example).
  VALUE :: [15, 100, 90, 60, 40, 15, 10,  1]
fills the VALUE array as follows:
VALUE(1) gets the value 15; VALUE(2) gets the value 100; ..., VALUE(8) gets the value 1.
For a 2-dimensional array such as
 declarations
  EE: array(1..2, 1..3) of real
 end-declarations
we might write
 EE:: [11, 12, 13,
       21, 22, 23 ]
which of course is the same as
 EE:: [11, 12, 13, 21, 22, 23]
but much more intuitive. Mosel places the values in the tuple into EE `going across the rows', with the last subscript varying most rapidly. For higher dimensions, the principle is the same. If the index sets of an array are other than ranges they must be given when initializing the array with data, in the case of ranges this is optional. Equivalently to the above we may write
  VALUE :: (ITEMS)[15, 100, 90, 60, 40, 15, 10,  1]
 EE:: (1..2, 1..3)[11, 12, 13,21, 22, 23 ]
or even initialize the two-dimensional array EE rowwise:
 EE:: (1, 1..3)[11, 12, 13]
 EE:: (2, 1..3)[21, 22, 23 ]
Summations:
  MaxVal:= sum(i in Items) VALUE(i)*x(i)
defines a linear expression called MaxVal as the sum

_{i Items}

VALUE_i·x_i
Naming constraints: Optionally, constraints may be named (as in the chess set example). In the remainder of this manual, we shall name constraints only if we need to refer to them at other places in the model. In most examples, only the objective function is named (here MaxVal) — to be able to refer to it in the call to the optimization (here maximize(MaxVal)).
Simple looping:
  forall(i in ITEMS) take(i) is_binary
illustrates looping over all values in an index range. Recall that the index range ITEMS is 1, ..., 8, so the statement says that take(1), take(2), ..., take(8) are all binary variables.
There is another example of the use of forall at the penultimate line of the model when writing out all the solution values.
Integer Programming variable types: To make an mpvar variable, say variable xbinvar, into a binary (0/1) variable, we just have to say
  xbinvar is_binary
To make an mpvar variable an integer variable, i.e. one that can only take on integral values in a MIP problem, we would have
  xintvar is_integer
The burglar problem revisited

Consider this model (burglari.mos):
model "Burglar (index set)"
 uses "mmxprs"

 declarations
  WTMAX = 102                    ! Maximum weight allowed
  ITEMS = {"camera", "necklace", "vase", "picture", "tv", "video", 
           "chest", "brick"}     ! Index set for items
  
  VALUE: array(ITEMS) of real    ! Value of items
  WEIGHT: array(ITEMS) of real   ! Weight of items
  
  take: array(ITEMS) of mpvar    ! 1 if we take item i; 0 otherwise
 end-declarations

 VALUE("camera")  := 15;  WEIGHT("camera")  :=  2
 VALUE("necklace"):=100;  WEIGHT("necklace"):= 20
 VALUE("vase")    := 90;  WEIGHT("vase")    := 20
 VALUE("picture") := 60;  WEIGHT("picture") := 30
 VALUE("tv")      := 40;  WEIGHT("tv")      := 40
 VALUE("video")   := 15;  WEIGHT("video")   := 30
 VALUE("chest")   := 10;  WEIGHT("chest")   := 60
 VALUE("brick")   :=  1;  WEIGHT("brick")   := 10

! Objective: maximize total value
 MaxVal:= sum(i in ITEMS) VALUE(i)*take(i) 

! Weight restriction
 sum(i in ITEMS) WEIGHT(i)*take(i) <= WTMAX

! All variables are 0/1
 forall(i in ITEMS) take(i) is_binary  

 maximize(MaxVal)                 ! Solve the MIP-problem

! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 forall(i in ITEMS)  writeln(" take(", i, "): ", getsol(take(i)))
end-model
What have we changed? The answer is, `not very much'.
String indices:
  ITEMS={"camera", "necklace", "vase", "picture", "tv", "video", 
         "chest", "brick"}
declares that this time ITEMS is a set of strings. The indices now take the string values `camera', `necklace' etc. Since string index sets have no fixed ordering like the range set we have used in the first version of the model, we now need to initialize every data item separately, or alternatively, write out the index sets when defining the array values, such as
 VALUE :: (["camera", "necklace", "vase", "picture", "tv", "video", 
            "chest", "brick"])[15,100,90,60,40,15,10,1]
 WEIGHT:: (["camera", "necklace", "vase", "picture", "tv", "video", 
            "chest", "brick"])[2,20,20,30,40,30,60,10]
If we run the model, we get
Solution:
 Objective: 280
 take(camera): 1
 take(necklace): 1
 take(vase): 1
 take(picture): 1
 take(tv): 0
 take(video): 1
 take(chest): 0
 take(brick): 0
Continuation lines:
Notice that the statement
  ITEMS={"camera", "necklace", "vase", "picture", "tv", "video", 
         "chest", "brick"}
was spread over two lines. Mosel is smart enough to recognize that the statement is not complete, so it automatically tries to continue on the next line. If you wish to extend a single statement to another line, just cut it after a symbol that implies a continuation, like an operator (+, -, <=, ...) or a comma (,) in order to warn the analyzer that the expression continues in the following line(s). For example
 ObjMax:= sum(i in Irange, j in Jrange) TAB(i,j) * x(i,j) +
           sum(i in Irange) TIB(i) * delta(i)             +
           sum(j in Jrange) TUB(j) * phi(j)
Conversely, it is possible to place several statements on a single line, separating them by semicolons (like x1 <= 4; x2 >= 7).
A blending example

The model background

A mining company has two types of ore available: Ore 1 and Ore 2. The ores can be mixed in varying proportions to produce a final product of varying quality. For the product we are interested in, the `grade' (a measure of quality) of the final product must lie between the specified limits of 4 and 5. It sells for REV= £125 per ton. The costs of the two ores vary, as do their availabilities. The objective is to maximize the total net profit.

Model formulation

Denote the amounts of the ores to be used by use₁ and use₂. Maximizing net profit (i.e., sales revenue less cost COST_o of raw material) gives us the objective function:

_{o ORES}

(REV-COST_o) · use_o

We then have to ensure that the grade of the final ore is within certain limits. Assuming the grades of the ores combine linearly, the grade of the final product is:

_{o ORES} GRADE_o · use_o

_{o ORES} use_o

This must be greater than or equal to 4 so, cross-multiplying and collecting terms, we have the constraint:

_{o ORES}

(GRADE_o-4) · use_o 0

Similarly the grade must not exceed 5.

_{o ORES} GRADE_o · use_o

_{o ORES} use_o

5

So we have the further constraint:

_{o ORES}

(5-GRADE_o) · use_o 0

Finally only non-negative quantities of ores can be used and there is a limit to the availability AVAIL_o of each of the ores. We model this with the constraints:

o ORES: 0 use_o AVAIL_o

Implementation

The above problem description sets out the relationships which exist between variables but contains few explicit numbers. Focusing on relationships rather than figures makes the model much more flexible. In this example only the selling price REV and the upper/lower limits on the grade of the final product (MINGRADE and MAXGRADE) are fixed.

Enter the following model into a file blend.mos.
model "Blend" 
 uses "mmxprs" 

 declarations
  REV = 125                      ! Unit revenue of product
  MINGRADE = 4                   ! Minimum permitted grade of product
  MAXGRADE = 5                   ! Maximum permitted grade of product
  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)

  use: array(ORES) of mpvar      ! Quantities of ores used
 end-declarations

! Read data from file blend.dat
 initializations from 'blend.dat'
  COST
  AVAIL
  GRADE
 end-initializations

! Objective: maximize total profit
 Profit:= sum(o in ORES) (REV-COST(o))* use(o)

! Lower and upper bounds on ore quality
 sum(o in ORES) (GRADE(o)-MINGRADE)*use(o) >= 0
 sum(o in ORES) (MAXGRADE-GRADE(o))*use(o) >= 0

! Set upper bounds on variables (lower bound 0 is implicit)
 forall(o in ORES) use(o) <= AVAIL(o)

 maximize(Profit)                 ! Solve the LP-problem

 ! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 forall(o in ORES)  writeln(" use(" + o + "): ", getsol(use(o)))

end-model
The file blend.dat contains the following:
! Data file for 'blend.mos'
COST: [85 93]
AVAIL: [60 45]
GRADE: [2.1 6.3]
The initializations from / end-initializations block is new here, telling Mosel where to get data from to initialize named arrays. The order of the data items in the file does not have to be the same as that in the initializations block; equally acceptable would have been the statements
initializations from 'blend.dat'
 AVAIL GRADE COST
end-initializations
Alternatively, since all data arrays have the same indices, they may be given in the form of a single record, such as BLENDDATA in the following data file blendb.dat:
        !   [COST AVAIL GRADE]
BLENDDATA: [ [85   60   2.1]
             [93   45   6.3] ]
In the initializations block we need to indicate the label of the data record and in which order the data of the three arrays is given:
initializations from 'blendb.dat'
 [COST,AVAIL,GRADE] as 'BLENDDATA'
end-initializations
Re-running the model with new data

There is a problem with the model we have just presented — the name of the file containing the costs date is hard-wired into the model. If we wanted to use a different file, say blend2.dat, then we would have to edit the model, and recompile it.

Mosel has parameters to help with this situation. A model parameter is a symbol, the value of which can be set just before running the model, often as an argument of the run command of the command line interpreter.
model "Blend 2" 
 uses "mmxprs" 

 parameters
  DATAFILE="blend.dat"
 end-parameters

 declarations
  REV = 125                      ! Unit revenue of product
  MINGRADE = 4                   ! Minimum permitted grade of product
  MAXGRADE = 5                   ! Maximum permitted grade of product
  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)

  use: array(ORES) of mpvar      ! Quantities of ores used
 end-declarations

! Read data from file
 initializations from DATAFILE
  COST
  AVAIL
  GRADE
 end-initializations

 ...

end-model
The parameter DATAFILE is recognized as a string, and its default value is specified. If we have previously compiled the model into say blend2.bim, then the command
mosel -c "load blend2; run DATAFILE='blend2.dat'"
will read the cost data from the file we want. Or to compile, load, and run the model using a single command:
mosel -c "exec blend2 DATAFILE='blend2.dat'"
Notice that a model only takes a single parameters block that must follow immediately after the uses statement(s) at the beginning of the model.

Reading data from spreadsheets and databases

It is quite easy to create and maintain data tables in text files but in many industrial applications data are provided in the form of spreadsheets or need to be extracted from databases. So there is a facility in Mosel whereby the contents of ranges within spreadsheets may be read into data tables and databases may be accessed. It requires an additional authorization in your Xpress-MP license.

On the Dash website, separate documentation is provided for the SQL/ODBC interface (Mosel module mmodbc): the whitepaper Using ODBC with Mosel explains how to set up an ODBC connection and discusses a large number of examples showing different SQL/ODBC features; the whitepaper Generalized file handling in Mosel also contains several examples of the use of ODBC. To give you a flavor of how Mosel's ODBC interface may be used, we now read the data of the blending problem from a spreadsheet and then later from a database.

The ODBC technology is a generic means for accessing databases and certain spreadsheets such as Microsoft Excel also support (a reduced set of) ODBC functionality. As an alternative to ODBC, Mosel also provides a specific interface to Excel spreadsheets, an example of which is shown below (Section Excel spreadsheets). This interface that supports all basic tasks of data exchange tends to be slightly more efficient due to its more direct access to the spreadsheet and we recommend its use if you work exclusively with Excel data.

Spreadsheet example

Let us suppose that in a Microsoft Excel spreadsheet called blend.xls you have inserted the following into the cells indicated:

Table 3.1: Spreadsheet example data
A B C D E F

1

2 ORES COST AVAIL GRADE

3 1 85 60 2.1

4 2 93 45 6.3

5

and called the range B2:E4 MyRange.

You need to make sure that the Excel ODBC driver is installed on your computer (Windows 2000 or XP: Start Settings Control Panel Administrative Tools Data Sources (ODBC) ODBC drivers).

The following model reads the data for the arrays COST, AVAIL, and GRADE from the Excel range MyRange. Note that we have added "mmodbc" to the uses statement to indicate that we are using the Mosel SQL/ODBC module.
model "Blend 3" 
 uses  "mmodbc", "mmxprs" 

 declarations
  REV = 125                      ! Unit revenue of product
  MINGRADE = 4                   ! Minimum permitted grade of product
  MAXGRADE = 5                   ! Maximum permitted grade of product
  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)

  use: array(ORES) of mpvar      ! Quantities of ores used
 end-declarations

! Read data from spreadsheet blend.xls
 initializations from "mmodbc.odbc:blend.xls"
  [COST,AVAIL,GRADE] as "MyRange"
 end-initializations
 
 ...
 
end-model
Instead of using the initializations block that automatically generates SQL commands for reading and writing data it is also possible to employ SQL statements in Mosel models. The initializations block above is equivalent to the following sequence of SQL statements:
 SQLconnect('DSN=Excel Files; DBQ=blend.xls')
 SQLexecute("select * from MyRange ", [COST,AVAIL,GRADE])
 SQLdisconnect
The SQL statement "select * from MyRange" says `select everything from the range called MyRange'. By using SQL statements directly in the Mosel model it is possible to have much more complex selection statements than the ones we have used.

Database example

If we use Microsoft Access, we might have set up an ODBC DSN called MSAccess, and suppose we are extracting data from a table called MyTable in the database blend.mdb. There are just the four columns ORES, columns COST, AVAIL, and GRADE in MyTable, and the data are the same as in the Excel example above. We modify the example above to be
model "Blend 4" 
 uses  "mmodbc", "mmxprs" 

 declarations
  REV = 125                      ! Unit revenue of product
  MINGRADE = 4                   ! Minimum permitted grade of product
  MAXGRADE = 5                   ! Maximum permitted grade of product
  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)

  use: array(ORES) of mpvar      ! Quantities of ores used
 end-declarations

! Read data from database blend.mdb
 initializations from "mmodbc.odbc:blend.mdb"
  [COST,AVAIL,GRADE] as "MyTable"
 end-initializations
 
 ...
 
end-model
To use other databases, for instance a mysql database (let us call it blend), we merely need to modify the connection string — provided that we have given the same names to the data table and its columns:
 initializations from "mmodbc.odbc:DSN=mysql;DB=blend"
ODBC, just like Mosel's text file format, may also be used to output data. The reader is referred to the ODBC/SQL documentation for more detail.

Excel spreadsheets

We shall work once more with the Microsoft Excel spreadsheet called blend.xls shown in Table Spreadsheet example data where we have defined the range B2:E4 MyRange and added a second range B3:E4 (that is, the same as the first without its header line) named MyRangeNoHeader.

This spreadsheet can be accessed directly (that is, without ODBC) from our Mosel model using a similar syntax to what we have seen for ODBC. The corresponding Mosel model looks as follows (notice that we still use the Mosel module mmodbc).
model "Blend 3 (Excel)" 
 uses  "mmodbc", "mmxprs" 

 declarations
  REV = 125                      ! Unit revenue of product
  MINGRADE = 4                   ! Minimum permitted grade of product
  MAXGRADE = 5                   ! Maximum permitted grade of product
  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)

  use: array(ORES) of mpvar      ! Quantities of ores used
 end-declarations

! Read data from spreadsheet blend.xls
 initializations from "mmodbc.excel:blend.xls"
  [COST,AVAIL,GRADE] as "MyRangeNoHeader"
 end-initializations
 
 ...
 
end-model
The only two modifications we have made are quite subtle: in the filename we have replaced mmodbc.odbc by mmodbc.excel and we now use a data range without header line (MyRangeNoHeader). It is also possible to work with the same range (MyRange) as we have used for the ODBC connection by adding the option skiph in the initializations block:
 initializations from "mmodbc.excel:blend.xls"
  [COST,AVAIL,GRADE] as "skiph;MyRange"
 end-initializations
Instead of naming the ranges in the spreadsheet it is equally possible to work directly with the cell references (including the worksheet name, that is, `Sheet1' in our case):
 initializations from "mmodbc.excel:blend.xls"
  [COST,AVAIL,GRADE] as "[Sheet1$B3:E4]"
 end-initializations
[Next] [Index]

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