FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Knapsack

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 explanation of this example: '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' (d2ship.mos)

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

knapsack_graph.mos

(!******************************************************
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) 2008 Fair Isaac Corporation
Creation: 2003, rev. Sep. 2017
*******************************************************!)

model Knapsack
uses "mmxprs", "mmsvg"

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

setrandseed(7)
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))

! Draw the solution
cumw:=0.0; cump:=0.0
forall(i in Items | getsol(x(i))>0) do
svgsetstyle(SVG_STROKE,SVG_NONE)
cumw+=WEIGHT(i)/WTMAX
cump+=VALUE(i)/getobjval
end-do