Example problem

The following small knapsack problem will be used as an example in the next sections.

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.

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.

The following Mosel model (burglar2.mos) implements this problem. In this implementation data are read from the text file burglar.dat. Note that the decision variables are declared after the initialization of the data, that is, at a point in the model where the contents of the set ITEMS is known. If an array is declared before its index sets are known it is created as a dynamic array. Dynamic arrays of basic types (such as VALUE and WEIGHT) grow by adding data entries, but for dynamic arrays of decision variables the entries need to be created explicitly once the index sets are known. By moving the declaration of the variables after the initialization of the data we can avoid this.

model Burglar2
 uses "mmxprs"

 declarations
  WTMAX = 102                    ! Maximum weight allowed
  ITEMS: set of string           ! Index set for items
  VALUE: array(ITEMS) of real    ! Value of items
  WEIGHT: array(ITEMS) of real   ! Weight of items
 end-declarations

 initializations from "burglar.dat"
  [VALUE,WEIGHT] as "BurgData"
 end-initializations

 declarations
  take: array(ITEMS) of mpvar    ! 1 if we take item i; 0 otherwise
 end-declarations

! 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

! Solution output
 forall(i in ITEMS) SOLTAKE(i):= getsol(take(i))

 writeln("Solution:\n Objective: ", getobjval)
 writeln(SOLTAKE)

 initializations to "burglarout.txt"
  SOLTAKE
 end-initializations

end-model

The data file burglar.dat read by this model has the following contents.

! Data file for `burglar2.mos'
          ! Item      Value  Weight
BurgData: [(camera)    [ 15   2]
           (necklace)  [100  20]
           (vase)      [ 90  20]
           (picture)   [ 60  30]
           (tv)        [ 40  40]
           (video)     [ 15  30]
           (chest)     [ 10  60]
           (brick)     [  1  10]]

The solution is output to the file burglarout.txt via initializations to. This prints the array SOLTAKE to a text file in initializations format:

'SOLTAKE': [('camera') 1 ('necklace') 1 ('vase') 1 ('picture') 1 ('tv') 0
 ('video') 1 ('chest') 0 ('brick') 0]