Dynamic Programming

Slide 1
 What is dynamic Programming?
Dynamic programming is both a mathematical optimization
method and an algorithmic paradigm. The method was developed
by Richard Bellman in the 1950s and has found applications in
numerous fields, from aerospace engineering to economics.
In both contexts it refers to simplifying a complicated problem by
breaking it down into simpler sub-problems in a recursive manner.
While some decision problems cannot be taken apart this way,
decisions that span several points in time do often break apart
recursively. Likewise, in computer science, if a problem can be
solved optimally by breaking it into sub-problems and then
recursively finding the optimal solutions to the sub-problems, then it
is said to have optimal substructure.

Slide 2
 Dynamic Programming: Contents

Dynamic Programming Overview

Dynamic Programming Notation
Backwards Recursion
3 Applications of Dynamic Programming
A Production and Inventory Control Problem

Slide 3
 The Main Idea of Dynamic Programming

The term Dynamic Programming comes from Control Theory,

not computer science. Programming refers to the use of tables
(arrays) to construct a solution.
In dynamic programming we usually reduce time by increasing
the amount of space

We solve the problem by solving sub-problems of increasing

size and saving each optimal solution in a table (usually).

The table is then used for finding the optimal solution to larger
problems.

Time is saved since each sub-problem is solved only once.

Slide 4
 When is Dynamic Programming used?
Used for problems in which an optimal solution for the
original problem can be found from optimal solutions to sub-
problems of the original problem
Often a recursive algorithm can solve the problem. But the
algorithm computes the optimal solution to the same sub-
problem more than once and therefore is slow.
The following two examples (Fibonacci and binomial
coefficient) have such a recursive algorithm
Dynamic programming reduces the time by computing the
optimal solution of a sub-problem only once and saving its
value. The saved value is then used whenever the same sub-
problem needs to be solved.

Slide 5
 Algorithmic Paradigms

Greedy Approach. Build up a solution incrementally,

myopically optimizing some local criterion.

Divide-and-conquer. Break up a problem into two sub-

problems, solve each sub-problem independently, and combine
solution to sub-problems to form solution to original problem.

Dynamic programming. Break up a problem into a series of

overlapping sub-problems, and build up solutions to larger and
larger sub-problems.

Slide 6
 Dynamic Programming History

❑ Richard Ernest Bellman. Pioneered the systematic study

of dynamic programming in the 1950s.

❑ Etymology.
• Dynamic programming = planning over time.
• Secretary of Defense was hostile to mathematical research.
• Bellman sought an impressive name to avoid confrontation.
• "it's impossible to use dynamic in a pejorative sense"
• "something not even a Congressman could object to"

Slide 7
 Dynamic Programming

Dynamic programming (DP) is an approach to

problem solving which permits decomposing of the
original problem into a series of several smaller sub-
problems.
To successfully apply DP, the original problem must
be viewed as a multistage decision problem. Defining
the stages is sometimes obvious, but at other times this
requires subtle reasoning.

Slide 8
 Overview of Serial Dynamic Programming

Dynamic programming (DP) is used to solve a wide variety of

discrete optimization problems such as scheduling, string-
editing, packaging, and inventory management.
Break problems into sub-problems and combine their solutions
into solutions to larger problems.
In contrast to divide-and-conquer, there may be relationships
across sub-problems.

Slide 9
 The steps of a dynamic programming

❑ Characterize the structure of an optimal solution

❑ Recursively define the value of an optimal solution
❑ Compute the value of an optimal solution in a bottom-up
fashion
❑ Construct an optimal solution from computed information

Slide 10
Dynamic Programming Applications
Areas.
• Bioinformatics.
• Control theory.
• Information theory.
• Operations research.
• Computer science: theory, graphics, AI, systems, ….

Some famous dynamic programming algorithms.

• Viterbi for hidden Markov models.
• Unix diff for comparing two files.
• Smith-Waterman for sequence alignment.
• Bellman-Ford for shortest path routing in networks.
• Cocke-Kasami-Younger for parsing context free grammars.

Slide 11
 Dynamic Programming

The power of DP is that one need solve only a small

portion of all sub-problems. This is due to Bellman's
principle of optimality. It states that regardless of
what decisions were made at previous stages, if the
decision to be made at stage n is to be part of an
overall optimal solution, then the decision made at
stage n must be optimal for all remaining stages.

Slide 12
 Dynamic Programming Notation

At each stage, n, of the dynamic program, there is a state

variable, xn, and an optimal decision variable, dn.
For each value of xn and dn at stage n, there is a return
function value, rn(xn, dn).
The output of the process at stage n is xn-1, the state
variable for stage n-1. It is calculated by a stage
transformation function, tn(xn, dn).
The optimal value function, fn(xn), is the cumulative return
starting at stage n in state xn and proceeding to stage 1
under an optimal policy (strategy).

Slide 13
 Backwards Recursion

Generally, a dynamic programming problem is solved by

starting at the final stage and working backwards to the
initial stage. This is called backwards recursion.
The following recursion relation can be used to
operationalize the principle of optimality:
fn(xn) = MAX {rn(xn, dn) + fn -1(tn(xn , dn))}
dn

A problem is solved beginning at stage 0 with the

boundary condition f0(x0) = 0, and working backwards to
the last stage, N.

Slide 14
 Three Applications of
Dynamic Programming Problems
Shortest Route Problem
In solving a shortest route problem using dynamic
programming, one should consider the network as a series
of stages with a unique subset of nodes corresponding to
each stage. The state variables correspond to the different
nodes at each stage.

Slide 15
 Three Applications of
Dynamic Programming Problems

Knapsack or Cargo Loading Problem

The knapsack problem seeks to determine the optimal
number of each of N items (which must not be fractional) to
select in order to maximize profit subject to an overall
capacity constraint. In solving a knapsack problem using
dynamic programming, the stages correspond to the different
items being placed into a knapsack. The state variables
correspond to the capacity available at the stage.

Slide 16
 Three Applications of
Dynamic Programming Problems
Production and Inventory Control Problems
In production and inventory control problems, the stages
correspond to time periods and the state variables generally
will refer to the amounts of inventory on hand at the
beginning of each stage.

Slide 17
 Example: Dicom Corporation
Production and Inventory Control Problem
Dicom Corporation wishes to determine a production
schedule for its new Model 44/12 virtual memory computer.
Because of differences in parts availability and spare
production capacity, the cost of producing the machines will
vary from month to month. These costs and other data are
shown on the next slide.
The holding cost for each unsold machine still in
inventory at the end of the month is $500,000. Corporate
policy dictates that the maximum number of machines allowed
in inventory at the end of any month is 8. Determine an
optimal 4 month production schedule for the Dicom Model
44/12.

Slide 18
 Example: Dicom Corporation

The following table gives these costs together with the

sales demand over the next 4 months as well as the
maximum possible production level per month.
Cost of Maximum
Production Production Sales
Per Machine Level Demand
Month (in $100,000's) for Month (in Units)
August 32 4 2
September 18 3 1
October 26 4 5
November 45 5 3

Slide 19
 Example: Dicom Corporation

4-Stage Dynamic Programming Problem

Working backwards, let stage 1 correspond to
November, stage 2 to October, etc. The following data
(costs are in $100,000's) can be inferred:
Product. Holding
Product. Storage Cost Cost
Month Dem. Capacity Capacity Per Unit Per unit
(n) Dn Pn Wn Cn Hn

1 3 5 8 45 5
2 5 4 8 26 5
3 1 3 8 18 5
4 2 4 8 32 5
Slide 20
 Example: Dicom Corporation

State Variable Defined

xn = number of computers in inventory at the beginning of
month n.
x4 = 0 (Since the computer is new, there will be no
inventory at the start of August.)
Decision Variable Defined
dn = production quantity for month n.
Stage Transformation Function
Then the stage transformations for months 0 through 4 can be
defined by: (Previous month's inventory) + (production this
month) - (demand this month), or
xn-1 = xn + dn - Dn

Slide 21
 Example: Dicom Corporation

Return Function
rn(xn, dn) = sum of the production and holding costs
for month n.
The production cost is the production cost per unit
multiplied by the number of units produced (dn).
The holding cost is the ending inventory for the month
multiplied by the holding cost per unit.
Hence, rn(xn,dn) = Cn dn + Hn(xn + dn - Dn)
This gives: r1(x1,d1) = 50d1 + 5x1 - 15
r2(x2,d2) = 31d2 + 5x2 - 25
r3(x3,d3) = 23d3 + 5x3 - 5
r4(x4,d4) = 37d4 + 5x4 - 10

Slide 22
 Dicom Corporation

Restrictions on xn and dn
• Since backordering is not allowed, we must be able to
meet the sales demand. That is, for month n:
xn + dn > Dn (1)
• Because there is a maximum storage of Wn at each stage n,
the total inventory at the end of any month cannot exceed
Wn . Hence, for each month it must be true that xn + dn -
Dn < Wn , or
xn + dn < Wn + Dn (2)
• The amount produced in any given month cannot exceed
the production capacity for that month, or
dn < Pn (3)

Slide 23
 Dicom Corporation

Optimal Value Function

fn(xn) = optimal return (minimal cost) for stages 1
through n given one starts stage n with xn
computers in inventory

fn(xn) = MIN {rn(xn, dn) + fn -1(xn -1)}

dn

where the dn is constrained by restrictions (1), (2), and

(3).

Slide 24
 Dicom Corporation

Stage 1
Starting at stage 1 (November), since f0(x0) = 0 is a
boundary condition, then,
f1(x1) = MIN r1(x1, d1)
d1
Using the expression for r1(x1, d1) and restrictions (1),
(2), and (3),
f1(x1) = MIN 5x1 + 50d1 - 15
s.t. x1 + d1 > 3 (1)
x1 + d1 < 11 (2)
d1 < 5 (3)
and, d1 > 0

Slide 25
 Example: Dicom Corporation

Tabulated Values for 50d1 +5x1 -15

d1
x1 0 1 2 3 4 5 d1* f1(x1)

0 135 185 235 3 135

1 90 140 190 240 2 90
2 45 95 145 195 245 1 45
3 0 50 100 150 200 250 0 0

Note that having x1 > 3 would result in Dicom having

computers in inventory at the end of November which is
undesirable.

Slide 26
 Example: Dicom Corporation

Stage 2
f2(x2) = MIN 5x2 + 31d2 -25 + f1(x1)
d2
Given the restrictions, the subproblem is:
f2(x2) = MIN 5x2+ 31d2 -25 + f1(x2+ d2 - 5)

s.t. x2 + d2 > 5 (1)

x2 + d2 < 13 (2)
d2 < 4 (3)
and d2 > 0

Slide 27
 Example: Dicom Corporation

Tabulated Values for 5x2 + 31d2 -25 + f1(x1)

d2
x2 0 1 2 3 4 d2* f2(x2) x2+d2*-5 = x1

1 239 4 239 0
2 213 199 4 199 1
3 187 173 159 4 159 2
4 161 147 133 119 4 119 3
5 135 121 107 93 3 93 3
6 95 81 67 2 67 3
7 55 41 1 41 3
8 15 0 15 3
Note that x2= 0 is infeasible.
Slide 28
 Example: Dicom Corporation

Stage 3
f3(x3) = MIN 5x3 + 23d3 - 5 + f2(x2)
d3

Given the restrictions, the subproblem is:

f3(x3) = MIN 5x3 + 23d3 - 5 + f2(x3 + d3 - 1)

s.t. x3 + d3 > 1 (1)

x3 + d3 < 9 (2)
d3 < 3 (3)
and d3 > 0

Slide 29
 Dicom Corporation

Tabulated Values for 5x3 + 23d3 - 5 + f2(x3 + d3 -1)

d3
x3 0 1 2 3 d3* f3(x3) x3 + d3*-1 = x2

0 280 263 3 263 2

1 263 245 228 3 228 3
2 244 227 210 193 3 193 4
3 209 192 175 172 3 172 5
4 174 157 154 151 3 151 6
5 139 136 133 130 3 130 7
6 118 115 112 109 3 109 8
7 97 94 91 1 91 8
8 76 73 1 73 8

Slide 30
 Dicom Corporation

Stage 4
f4(x4) = MIN 5x4 + 37d4 - 10 + f3(x3)
d4

Given the restrictions, the subproblem is:

f4(x4) = MIN 5x4 + 37d4 - 10 + f3(x4 + d4 - 2)

s.t. x4 + d4 > 2 (1)

x4 + d4 < 10 (2)
d4 < 4 (3)
and d4 > 0

Slide 31
 Dicom Corporation

Tabulated Values for 5x4 + 37d4 - 10 + f3(x4 + d4 - 2)

Since August starts with x4 = 0 inventory on hand,
compute table only for x4 = 0.
d4
x4 0 1 2 3 4 d4* f4 (x4 ) x4+d4*-2 = x3

0 327 329 331 2 327 0

Slide 32
 Dicom Corporation

Solution Summary
Working backwards through the tables, one can
determine the optimal solution that gives the minimum cost
of $327 x 100,000 = $32,700,000.
Inventory On-
Hand Beginning
Stage Month Produce (dn*) Next Month xn-1

4 August 2 0
3 September 3 2
2 October 4 1
1 November 2 0

Slide 33
 Example 2: Mills Manufacturing Company
Mills Manufacturing Company has a production and inventory
control problem. The available data for the next 3 months planning
period are presented below:
Production Holding
Production Storage Cost Cost
Month Demand Capacity Capacity Per Unit Per unit

1 20 30 40 2.00 0.30
2 30 20 30 1.50 0.30
3 30 30 20 2.00 0.20
Using the Dynamic programming approach, find the optimal
production quantities and inventory levels in each period for the
Mills Manufacturing Company. Assume there is beginning
inventory of 10 units on hand at the beginning of first month
Slide 34
 Example 2 Cont.

Solution: 3-Stage Dynamic Programming Problem

Working backwards, let stage 1 correspond to Month-
1, stage 2 to Month-2, and stage 3 to Month-3. The
following data can be inferred:
Product. Holding
Product. Storage Cost Cost
Month Dem. Capacity Capacity Per Unit Per unit
(n) Dn Pn Wn Cn Hn

1 20 30 40 2.00 0.30
2 30 20 30 1.50 0.30
3 30 30 20 2.00 0.20

Slide 35
 Example 2 Cont.

X3 =10

Stage-3 (Month-1)
D3=20, P3 = 30, W3=40, d3 =?, r3(x3,d3)

Stage-2 (Month-2)
D2=30, P2 = 20, W2=30, d2 =?, r2(x2,d2)

Stage-1 (Month-3)
D1=30, P1 = 30, W1=20, d1 =?, r1(x1,d1)

Slide 36
 Example 2 Cont.
State Variable Defined
xn = number of units in inventory at the beginning of
month n.
x3 = 10
Decision Variable Defined
dn = production quantity for month n.
Stage Transformation Function
Then the stage transformations for months 0 through 3 can be
defined by: (Previous month's inventory) + (production this
month) - (demand this month), or
xn-1 = xn + dn - Dn
x2 = x3 + d3 – D3 = x3 + d3 – 20
x1 = x2 + d2 – D2 = x2 + d2 – 30
x0 = x1 + d1 – D1 = x1 + d1 – 30 Slide 37
 Example 2 Cont.

Return Function
rn(xn, dn) = sum of the production and holding costs
for month n.
The production cost is the production cost per unit
multiplied by the number of units produced (dn).
The holding cost is the ending inventory for the month
multiplied by the holding cost per unit.
Hence, rn(xn,dn) = Cn dn + Hn(xn + dn - Dn)
This gives: r1(x1, d1) = 2.2d1 + 0.2x1 - 6
r2(x2, d2) = 1.8d2 + 0.3x2 - 9
r3(x3, d3) = 2.3d3 + 0.3x3 - 6

Slide 38
 Example 2 Cont.

Restrictions on xn and dn
• Since backordering is not allowed, we must be able to
meet the sales demand. That is, for month n:
xn + dn > Dn (1)
• Because there is a maximum storage of Wn at each stage n,
the total inventory at the end of any month cannot exceed
Wn . Hence, for each month it must be true that xn + dn -
Dn < Wn , or
xn + dn < Wn + Dn (2)
• The amount produced in any given month cannot exceed
the production capacity for that month, or
dn < Pn (3)

Slide 39
 Example 2 Cont.

Optimal Value Function

fn(xn) = optimal return (minimal cost) for stages 1
through n given one starts stage n with xn
computers in inventory

fn(xn) = MIN {rn(xn ,dn) + fn -1(xn -1)}

dn

where the dn is constrained by restrictions (1), (2), and

(3).

Slide 40
 Example 2 Cont.

Stage 1
Starting at stage 1 (Month 3), since f0(x0) = 0 is a
boundary condition, then,
f1(x1) = MIN r1(x1, d1)
d1
Using the expression for r1(x1, d1) and restrictions (1),
(2), and (3),
f1(x1) = MIN 0.2x1 + 2.2d1 - 6
s.t. x1 + d1 < 50 (1)
d1 < 30 (2)
x1 + d1 > 30 (3)
and, d1 > 0

Slide 41
 Example 2 Cont.

Tabulated Values for 0.2x1 + 2.2d1 -6

d1
x1 f1(x1) = 0.2x1 + 2.2d1 - 6

0 30 60
10 20 40
20 10 20
30 0 0

Note that x1 = 30 we consider warehouse capacity at stage 2;

d1 = 30 we consider production capacity at stage 1; and
production runs are computed in multiple of 10 units.

Slide 42
 Example 2 Cont.

Stage 2
f2(x2) = MIN 0.3x2 + 1.8d2 -9 + f1(x1)
d2
Given the restrictions, the sub-problem is:
f2(x2) = MIN 0.3x2 + 1.8d2 -9 + f1(x2+ d2 - 30)

s.t. x2+ d2 < 60 (1)

d2 < 20 (2)
x2+ d2 > 30 (3)
and d2 >0

Slide 43
 Example 2 Cont.

Tabulated Values for 0.3x2 + 1.8d2 -9 + f1(x1)

d2
x2 0 10 20 d2* f2(x2) x2+d2*-30 = x1

0 - - - M -
10 - - 90 20 90 0
20 - 75 73 20 73 10
30 60 58 56 20 56 20
40 43 41 39 20 39 30

Slide 44
 Example 2 Cont.

Stage 3
f3(x3) = MIN 0.3x3 + 2.3d3 - 6 + f2(x2)
d3

Given the restrictions, the subproblem is:

f3(x3) = MIN 0.3x3 + 2.3d3 - 6 + f2(x3 + d3 - 20)

s.t. x3 + d3 < 60 (1)

d3 < 30 (2)
x3 + d3 > 20 (3)
and d3 > 0

Slide 45
 Example 2 Cont.

Tabulated Values for 0.3x3 + 2.3d3 - 6 + f2(x3 + d3 -20)

d3
x3 0 10 20 30 d3* f3(x3) x3 + d3*-20 = x2

10 - M 133 139 20 133 10

Therefore, when x3 = 10, then d3* = 20 and x2 = 10

when x2 = 10, then d2* = 20 and x1 = 0
when x1 = 0, then d1* = 30 and x0 = 0

Slide 46
 Example 2 Cont.

Month Beginning Production Production Ending Holding Total Cost

Inventory Cost Inventory Cost
1 10 20 40 10 3 43
2 10 20 30 0 0 30
3 0 30 60 0 0 60
Total 130 133

Hence Mills Manufacturing Company should produce 20 units

in Month-1, 20 units in Month-2 and 30 units in Month-3 and
total cost $133 will be incurred.

Slide 47
Slide 48