(!******************************************************
   Mosel Example Problems
   ======================

   file knapsack.mos
   `````````````````
   TYPE:         Knapsack problem
   DIFFICULTY:   1
   FEATURES:     simple IP problem, formulation of knapsack constraints,
                 model parameters, function 'random'
   DESCRIPTION:  We wish to choose among items of different value and
                 weight those that result in the maximum total value for 
                 a given weight limit.     
   FURTHER INFO: `Mosel User Guide', Section 2.1 `The burglar problem';
                 `Applications of optimization with Xpress-MP', 
                 Section 5.2 `Modeling with Mosel'.
                 Similar problem: Section 9.2 `Barge loading'

   (c) 2003 Dash Associates
*******************************************************!)

model Knapsack
 uses "mmxprs"                      ! Load the optimizer library

 parameters
  NUM=8                             ! Number of items
  MAXVAL=100                        ! Maximum value
  MAXWEIGHT=80                      ! Maximum weight
  WTMAX=102                         ! Max weight allowed for haul
 end-parameters

 declarations
  Items=1..NUM                      ! Index range for items
  VALUE: array(Items) of real       ! Value of items
  WEIGHT: array(Items) of real      ! Weight of items

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

 forall(i in Items) do
  VALUE(i):=50+random*MAXVAL
  WEIGHT(i):=1+random*MAXWEIGHT
 end-do

 MaxVal:= sum(i in Items) VALUE(i)*x(i)  ! Objective: maximize total value

                                    ! Weight restriction
 WtMax:= sum(i in Items) WEIGHT(i)*x(i) <= WTMAX 

 forall(i in Items) x(i) is_binary  ! All x are 0/1
  
 maximize(MaxVal)                   ! Solve the MIP-problem

                                    ! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 writeln("Item  Weight  Value")
 forall(i in Items)  writeln(i, ": ", getsol(x(i)), strfmt(WEIGHT(i),8,2), strfmt(VALUE(i),8,2))

end-model