Project Management
ENGG1400
David Rey
Research Center for Integrated Transport Innovation (rCITI)
School of Civil and Environmental Engineering
UNSW Australia
Knapsack Problem
Dynamic Programming Approach
Outline
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Outline
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Reminder - The Knapsack Problem
Consider the following problem: Given a set of items, each with a
weight and a value, find the collection of items with the maximal
value such that the total weight does not exceed a specified limit.
Famous optimization problem with multiple real-world applications:
Portfolio management
Cargo/container loading
Waste minimization in cutting stock
Hiker/burglar knapsack preparation
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Reminder - The Knapsack Problem: variants
There are many types of Knapsack Problems, the three most
commonly considered are:
1
0-1 Knapsack Problem: an item can either be taken or not
(e.g. loading of wine bottles in a cargo)
Fractional Knapsack Problem: a proportion of an item can
be taken (e.g. packing of bulk wood)
Unbounded Knapsack Problem: no limit in the availability
of the items (e.g. financial investment) Note: can be 0-1
or Fractional
Today 0-1 Knapsack problems.
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Formulation for the 0-1 Knapsack Problem
The capacity of the knapsack is C
The set of items is N = {1, . . . , n}
The weight of item i N is wi
The value of item i N is vi
The quantity of item i N which is taken is xi (decision
variable)
Bounded problem:
Each item is available in limited
quantity, we normalize the
quantity taken: xi {0, 1}
Unbounded problem:
Each item is available in
unlimited quantity, the quantity
taken is non-negative:
xi {0, 1, 2, . . .}
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Objective and Constraints for the 0-1 Knapsack
Objective function
The objective is to maximize the total value of the knapsack:
X
max
xi vi
iN
Capacity constraint
The total weight of the items taken must not exceed the capacity
of the knapsack:
X
xi wi C
iN
Decision variables domain
Bounded: xi {0, 1}, i N
Unbounded: xi {0, 1, 2, . . .}, i N
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Formulation for the 0-1 Knapsack Problem
Bounded model
max V =
xi vi
Unbounded model
X
max V =
xi vi
iN
subject to:
X
xi wi C
iN
subject to:
X
iN
xi {0, 1},i N
xi wi C
iN
xi {0, 1, 2, . . .},i N
Today Focus on the Bounded problem.
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Example for the 0-1 Knapsack Problem
item
w
1 (rosemary) 10
2 (paprika)
20
3 (oregano)
30
4 (curry)
40
5 (saffron)
50
Capacity = 100
v
20
30
66
40
70
v /w
2
1.5
2.2
1
1.4
(w = weight, v = value)
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Example for the 0-1 Knapsack Problem
item
w
1 (rosemary) 10
2 (paprika)
20
3 (oregano)
30
4 (curry)
40
5 (saffron)
50
Capacity = 100
v
20
30
66
40
70
v /w
2
1.5
2.2
1
1.4
(w = weight, v = value)
Lets compare the optimal solution for 0-1/Fractional problems:
0-1 case x? = [0, 1, 1, 0, 1]: V = 30 + 66 + 70 = 166
used capacity is 20 + 30 + 50 = 100
Fractional case x? = [1, 1, 1, 0, 4/5]: V = 172
used capacity is 10 + 20 + 30 + 50 4/5 = 100
Different solutions, lesser value for the 0-1 problem
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Can we use the greedy algorithm for the 0-1 Problem? (1)
item
w
1 (rosemary) 10
2 (paprika)
20
3 (oregano)
30
4 (curry)
40
5 (saffron)
50
Capacity = 100
v
20
30
66
40
70
v /w
2
1.5
2.2
1
1.4
Greedy algorithm for the (bounded)
0-1 knapsack problem:
Sort items by decreasing v /w
ratio
Take the highest v /w ratio
item (if possible)
Repeat until the knapsack is full
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Can we use the greedy algorithm for the 0-1 Problem? (1)
item
w
1 (rosemary) 10
2 (paprika)
20
3 (oregano)
30
4 (curry)
40
5 (saffron)
50
Capacity = 100
v
20
30
66
40
70
v /w
2
1.5
2.2
1
1.4
Greedy algorithm for the (bounded)
0-1 knapsack problem:
Sort items by decreasing v /w
ratio
Take the highest v /w ratio
item (if possible)
Repeat until the knapsack is full
Initial knapsack weight W = 0
1. Take the oregano W = 30, V = 66
2. Take the rosemary W = 40, V = 86
3. Take the paprika W = 60, V = 116
4. Cant take the saffron, so take the curry W = 100, V = 156
not the optimal solution (optimal cost is 166)!
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Can we use the greedy algorithm for the 0-1 Problem? (1)
item
w
1 (rosemary) 10
2 (paprika)
20
3 (oregano)
30
4 (curry)
40
5 (saffron)
50
Capacity = 100
v
20
30
66
40
70
v /w
2
1.5
2.2
1
1.4
Greedy algorithm for the (bounded)
0-1 knapsack problem:
Sort items by decreasing v /w
ratio
Take the highest v /w ratio
item (if possible)
Repeat until the knapsack is full
So is the greedy algorithm any good for the 0-1 knapsack problem?
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Can we use the greedy algorithm for the 0-1 Problem? (2)
Consider the following problem:
item w
1
5
2
100
Capacity =
v
50
100
100
v /w
10
1
What happens when we use the greedy algorithm?
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Can we use the greedy algorithm for the 0-1 Problem? (2)
Consider the following problem:
item w
1
5
2
100
Capacity =
v
50
100
100
v /w
10
1
What happens when we use the greedy algorithm?
Initial knapsack weight W = 0
1. Take item 1 W = 5, V = 50
2. Cant take item 2 because 5 + 100 > W
We get a knapsack of value 50 whereas taking item 2 would have
given a knapsack of value 100!
Knapsack Problem
Dynamic Programming Approach
Outline
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Principles of Dynamic Programming
Dynamic Programming (DP) is a method for solving
optimization problems
Requirement: need to be able to decompose the initial
problem into optimal sub-problems
Idea: solve a sub-problem and use the resulting solution to
solve a larger one
DP uses a recursive formulation to iteratively
solve the sub-problems
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Recursion: Computing the Fibonacci Sequence
The Fibonacci sequence is the sequence of integer numbers
starting from 0 and 1 such that the next number is the sum of its
two predecessors:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .
To compute the nth number in the Fibonacci sequence, we can
use a recursive formulation: let F (n) be the function that gives the
nth Fibonacci number with F (1) = 0 and F (2) = 1
F (n) = F (n 1) + F (n 2)
The above equation is a recursive function
because the same function is used within itself.
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Using DP for the 0-1 Knapsack Problem
Optimal sub-structure for the 0-1 Knapsack problem
The optimal solution of the sub-problem with up to k 1 items
and a reduced capacity c C is part of the optimal solution of the
sub-problem with up to k items and capacity c + wk .
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Using DP for the 0-1 Knapsack Problem
Optimal sub-structure for the 0-1 Knapsack problem
The optimal solution of the sub-problem with up to k 1 items
and a reduced capacity c C is part of the optimal solution of the
sub-problem with up to k items and capacity c + wk .
Why? Assume we solved all the problems (c = 0, . . . , C ) with the
first 3 items. If we consider taking the 4th item with weight w4
and a knapsack of reduced capacity of c = 8:
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Using DP for the 0-1 Knapsack Problem
Optimal sub-structure for the 0-1 Knapsack problem
The optimal solution of the sub-problem with up to k 1 items
and a reduced capacity c C is part of the optimal solution of the
sub-problem with up to k items and capacity c + wk .
Why? Assume we solved all the problems (c = 0, . . . , C ) with the
first 3 items. If we consider taking the 4th item with weight w4
and a knapsack of reduced capacity of c = 8:
if w4 > c (doesnt fit) the solution remains unchanged
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Using DP for the 0-1 Knapsack Problem
Optimal sub-structure for the 0-1 Knapsack problem
The optimal solution of the sub-problem with up to k 1 items
and a reduced capacity c C is part of the optimal solution of the
sub-problem with up to k items and capacity c + wk .
Why? Assume we solved all the problems (c = 0, . . . , C ) with the
first 3 items. If we consider taking the 4th item with weight w4
and a knapsack of reduced capacity of c = 8:
if w4 > c (doesnt fit) the solution remains unchanged
if w4 c (it fits) assume w4 = 3, then if taking up to 3 (first)
items with a reduced capacity of c w4 = 5 with the 4th item
is better than taking up to 3 (first) items with capacity of
c = 8 then we take the 4th item; otherwise we dont
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
DP Algorithm for the 0-1 Knapsack Problem
Define the m[i, c] as the maximum value that can be attained with
a capacity of c using items up to i (the first i items).
We can compute m[i, c] recursively as follows:
m[i, c] = m[i 1, c]
if wi > c
m[i, c] = max{m[i 1, c], m[i 1, c wi ] + vi }
if wi c
Computing m[n, C ] will give the optimal solution to the initial
knapsack problem.
Note that we can use a table to efficiently store the previous
computations (and save time and space).
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
w
1
2
3
4
5
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
v
20
30
66
40
70
0
-
1
-
Divide all weights and the knapsack
capacity by the greatest common
denominator (10 in this case) to simplify
the problem.
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
w
1
2
3
4
5
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
v
20
30
66
40
70
0
0
0
0
0
0
0
1
0
-
Initialize table with 0s: top row is 0s
because the value is 0 if there is no items;
left column is 0s because cant take any
items with 0 capacity
2
0
-
3
0
-
4
0
-
5
0
-
6
0
-
7
0
-
8
0
-
9
0
-
10
0
-
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
0
0
0
0
0
0
0
w
1
2
3
4
5
v
20
30
66
40
70
Determine m[1, c] for c = 1, . . . , 10
if w1 > c :
m[1, c] = m[0, c]
if w1 c :
m[1, c] = max{m[0, c], m[0, c 1] + 20}
1
0
20
-
2
0
20
-
3
0
20
-
4
0
20
-
5
0
20
-
6
0
20
-
7
0
20
-
8
0
20
-
9
0
20
-
10
0
20
-
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
0
0
0
0
0
0
0
w
1
2
3
4
5
v
20
30
66
40
70
Determine m[2, c] for c = 1, . . . , 10
if w2 > c :
m[2, c] = m[1, c]
if w2 c :
m[2, c] = max{m[1, c], m[1, c 2] + 30}
1
0
20
20
-
2
0
20
30
-
3
0
20
50
-
4
0
20
50
-
5
0
20
50
-
6
0
20
50
-
7
0
20
50
-
8
0
20
50
-
9
0
20
50
-
10
0
20
50
-
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
0
0
0
0
0
0
0
w
1
2
3
4
5
v
20
30
66
40
70
Determine m[3, c] for c = 1, . . . , 10
if w3 > c :
m[3, c] = m[2, c]
if w3 c :
m[3, c] = max{m[2, c], m[2, c 3] + 66}
1
0
20
20
20
-
2
0
20
30
30
-
3
0
20
50
66
-
4
0
20
50
86
-
5
0
20
50
96
-
6
0
20
50
116
-
7
0
20
50
116
-
8
0
20
50
116
-
9
0
20
50
116
-
10
0
20
50
116
-
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
0
0
0
0
0
0
0
w
1
2
3
4
5
v
20
30
66
40
70
Determine m[4, c] for c = 1, . . . , 10
if w4 > c :
m[4, c] = m[3, c]
if w4 c :
m[4, c] = max{m[3, c], m[3, c 4] + 40}
1
0
20
20
20
20
-
2
0
20
30
30
30
-
3
0
20
50
66
66
-
4
0
20
50
86
86
-
5
0
20
50
96
96
-
6
0
20
50
116
116
-
7
0
20
50
116
116
-
8
0
20
50
116
126
-
9
0
20
50
116
136
-
10
0
20
50
116
156
-
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Illustration of the DP Algorithm
item
1 (rosemary)
2 (paprika)
3 (oregano)
4 (curry)
5 (saffron)
Capacity = 10
m[i, c]
i =0
i =1
i =2
i =3
i =4
i =5
0
0
0
0
0
0
0
w
1
2
3
4
5
v
20
30
66
40
70
Determine m[5, c] for c = 1, . . . , 10
if w5 > c :
m[5, c] = m[4, c]
if w5 c :
m[5, c] = max{m[4, c], m[4, c 5] + 70}
1
0
20
20
20
20
20
2
0
20
30
30
30
30
3
0
20
50
66
66
66
4
0
20
50
86
86
86
5
0
20
50
96
96
96
6
0
20
50
116
116
116
7
0
20
50
116
116
116
8
0
20
50
116
126
136
9
0
20
50
116
136
156
10
0
20
50
116
156
166
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Summary on Knapsack problems
Both Fractional and 0-1 Knapsack problems can be solved
with AMPL workshop
Fractional Knapsack can also be solved with a greedy
algorithm or a DP algorithm
0-1 Knapsack can also be solved with a DP algorithm
In this course focus on solving Knapsack problems with
AMPL but you should be familiar with the greedy and the DP
algorithms
AMPL uses an optimization engine called CPLEX (works with
divide and conquer algorithms) which mechanics are outside
of the scope of the course
Knapsack Problem
Dynamic Programming Approach
Outline
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Cargo Loading Problem
Given a set of cargo and a container,
find the optimal collection of cargo to
load subject to capacity and loading
constraints
Similar to 0-1 Knapsack problem but with additional constraints
and/or subproblems.
Knapsack Problem
Dynamic Programming Approach
Cargo Loading Problem
Given a set of cargo and a container,
find the optimal collection of cargo to
load subject to capacity and loading
constraints
Loading constraints:
Load balance
Vertical stability
Load bearing
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Cargo Loading Problem
Given a set of cargo and a container,
find the optimal collection of cargo to
load subject to capacity and loading
constraints
Nested Knapsack problems:
For each cargo, one could solve a
Knapsack problem to decide what
to pack
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Cargo Loading Formulation
Simplified balanced-weight model for cargo loading:
the space of the container is discretized into slots:
S = {1, 2, 3, . . .}
each slot has a maximum capacity (in tons) that it can
support Bj , j S
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Cargo Loading Formulation: new variables
Simplified balanced-weight model for cargo loading:
Assignment Variables
Let yij be a binary variable defined as:
(
1 if item i is assigned to slot j
yij
0 otherwise
Load Balance Constraints
Let yij be a binary variable defined as:
X
yij = xi i N
jS
X
iN
yij wi Bj
j S
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Cargo Loading Model with Balance Constraints
Cargo Loading Model
max V =
xi vi
iN
subject to:
X
xi wi C
iN
yij = xi
i N
yij wi Bj
j S
xi {0, 1}
i N
yij {0, 1}
i N, j S
jS
X
iN
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Cargo Loading: Illustration
item i wi vi
1
8
10
2
5
20
3
3
30
4
6
40
5
5
50
6
7
10
7
2
20
8
9
30
9
4
40
10
1
50
Capacity: C = 40
S = {1, . . . , 8}
Load: Bj = 10, j
Logistics Problems
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Cargo Loading: Illustration
item i wi vi
1
8
10
2
5
20
3
3
30
4
6
40
5
5
50
6
7
10
7
2
20
8
9
30
9
4
40
10
1
50
Capacity: C = 40
S = {1, . . . , 8}
Load: Bj = 10, j
Optimal container value =
280
x? = [0, 1, 1, 1, 1, 0, 1, 1, 1, 1]
Capacity used: 35 tons
Allocation (y? ):
items 2 and 9 together
items 3 and 10 together
4 other items alone
6/8 slots used
Knapsack Problem
Dynamic Programming Approach
Logistics Problems
Summary
Knapsack models are very useful for project management: finance,
logistics, etc.
Fractional Knapsack used to represent problems with divisible
goods/items can be solved with a greedy algorithm by
sorting the items in decreasing value/weight ratio
0-1 Knapsack used to represent problems with indivisible
goods/items can be solved with a dynamic programming
algorithm (recursion, problem decomposition, optimal
sub-structure)
Project management decisions can often be modeled as
packing problems where a highest-value combination of
goods/items is sought
Next week vehicle routing (an operational logistics problem)
