Some illustrative examples

Topics covered in this chapter:

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 GRADEo · useo

∑o ∈ ORES useo

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 GRADEo · useo

∑o ∈ ORES useo

≤ 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 run blend2 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 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.

In addition to the documentation of the Mosel modules mmodbc and mmsheet in the Mosel language reference manual, you will find further detail and examples of using the SQL/ODBC and spreadsheet interfaces in other documents of the Xpress distribution: the whitepaper Using ODBC and other database interfaces 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 and spreadsheet interfaces 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 some spreadsheets such as certain versions of Microsoft Excel also support (a reduced set of) ODBC functionality. 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 should be used for working with Excel data. A generic alternative for working with spreadsheets in .xls, .xlsx, or .csv format, including on non-Windows platforms, is discussed in Section Generic spreadsheet example.

Excel spreadsheets

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 B3:E4 MyRange.

The following model reads the data for the arrays COST, AVAIL, and GRADE from the Excel range MyRange. Note that we have added "mmsheet" to the uses statement to indicate that we are using the Mosel spreadsheet module.

model "Blend 3"
 uses  "mmxprs", "mmsheet"

 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 "mmsheet.excel:blend.xls"
  [COST,AVAIL,GRADE] as "MyRange"
 end-initializations

 ...

end-model

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 "mmsheet.excel:blend.xls"
  [COST,AVAIL,GRADE] as "[Sheet1$B3:E4]"
 end-initializations

or alternatively, work with row and column counters:

 initializations from "mmsheet.excel:blend.xls"
  [COST,AVAIL,GRADE] as "[Sheet1$R3C2:R4C5]"
 end-initializations

And we can also select specific columns from a range:

 initializations from "mmsheet.excel:blend.xls"
  GRADE as "MyRange(#1,#4)"
 end-initializations

If the range definition contains the header line with column titles (so, MyRangeWithHeader is the area B2:E4) we can also select specific columns via their titles:

 initializations from "mmsheet.excel:blend.xls"
  GRADE as "skiph;MyRangeWithHeader(ORES,GRADE)"
 end-initializations

Database example

If we use Microsoft Access, we might have set up an ODBC DSN called MSAccess. Note: this is where to check whether the DSN is set up with Windows 2000 or XP: Start » Settings » Control Panel » Administrative Tools » Data Sources (ODBC) » ODBC drivers; on Windows 10 open the ODBC Data Source Administrator.
Suppose we are extracting data from a table called MyTable in the database blend.mdb. There are just the four columns ORES, 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

Note: as an alternative to working with Microsoft Access, you can use the built-in SQLite database that is available on all platforms supported by Mosel without any additional installation: replace the filename blend.mdb by blend.sqlite in the following examples.

model "Blend 4"
 uses  "mmxprs", "mmodbc"

 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

With ODBC, we can use the field names to select specific columns from a table:

 initializations from "mmodbc.odbc:blend.mdb"
  GRADE as "MyTable(ORES,GRADE)"
 end-initializations

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 in the model above is equivalent to the following sequence of SQL statements:

 SQLconnect('DSN=MSAccess; DBQ=blend.mdb')
 if not getparam("SQLsuccess"): exit(1)
 SQLexecute("select * from MyTable ", [COST,AVAIL,GRADE])
 SQLdisconnect

The SQL statement "select * from MyTable" says `select everything from the table called MyTable'. 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. Note that it is recommended to check the value of SQLsuccess after calls to individual SQL commands.

When working with a SQLite database it is sufficient to specify the database filename in the SQLconnect statement:

 SQLconnect('blend.sqlite')

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 and the Xpress whitepaper Using ODBC and other database interfaces with Mosel for more detail.

Generic spreadsheet example

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 B3:E4 MyRange.

This spreadsheet can be accessed via MS Excel as shown above. However, this access method is only available on platforms where Excel is installed. The module mmsheet also provides more generic interfaces for working with .xsl, .xlsx and CSV format files (usable, for example, under Linux or MacOS). The corresponding Mosel model looks as follows.

model "Blend 3 (spreadsheet)"
 uses "mmsheet", "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 "mmsheet.xls:blend.xls"
  [COST,AVAIL,GRADE] as "MyRange"
 end-initializations

 ...

end-model

The only modification we have made is quite subtle: in the filename we have replaced mmsheet.excel by mmsheet.xls.

Variant: Assuming that we have saved the data from our spreadsheet into the CSV format file blend.csv, we need to switch to the CSV interface for accessing this data file. A CSV file contains a single worksheet and it is not possible to define named ranges. We therefore now refer directly to the cells via the cell references (similarly to what has been shown for Excel in Section Excel spreadsheets but without stating a sheet name):

 initializations from "mmsheet.csv:blend.csv"
  [COST,AVAIL,GRADE] as "[B3:E4]"
 end-initializations

or alternatively, using row and column counters:

 initializations from "mmsheet.csv:blend.csv"
  [COST,AVAIL,GRADE] as "[R3C2:R4C5]"
 end-initializations