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:

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