Deterministic Dynamic Programming
Dynamic programming (DP) determines the
optimum solution of a multivariable problem by
decomposing it into stages, each stage comprising
a single-variable subproblem.
1
Deterministic Dynamic Programming
The advantage of the decomposition is that
the optimization process at each stage involves
one variable only, a simpler task computationally
than dealing with all the variables simultaneously.
2
Recursive Nature of Computations in DP
Computations in DP are done recursively, so
that the optimum solution of one subproblem is
used as an input to the next subproblem. By the
time the last subproblem is solved, the optimum
solution for the entire problem is at hand.
3
Recursive Nature of Computations in DP
The manner in which the recursive
computations are carried out depends on how
we decompose the original problem. In particular,
the subproblems are normally linked by common
constraints. As we move from one subproblem to
the next, the feasibility of these common
constraints must be maintained.
4
Shortest Route Problem
Example 9:
Suppose that you want to select the shortest
highway route between two cities. The network
in the next slide provides the possible routes
between the starting city at node 1 and the
destination city at node 7. The routes pass
through intermediate cities designated by nodes
2 to 6. 5
Shortest Route Problem
2 12
7 5
8 9
8
1 3 9 7
5
7 6 6
4 13
6
Shortest Route Problem
We can solve this problem by exhaustively
enumerating all the routes between nodes 1 and
7. However, in a large network, exhaustive
enumeration may be intractable computationally.
7
Shortest Route Problem
To solve the problem by DP, we first
decompose it into stages as delineated by the
vertical dashed lines in the next figure. Next, we
carry out the computations for each stage
separately.
8
Shortest Route Problem
2 2
12
7
5 5 9
8
8 7
1 3 3 9
5 6 6
7
6
13
4 4
9
Shortest Route Problem
2 2
12
7
5 5 9
8
8 7
1 3 3 9
5 6 6
7
6
13
4 4
10
Stage 1
Shortest Route Problem
2 2
12
7
5 5 9
8
8 7
1 3 3 9
5 6 6
7
6
13
4 4
11
Stage 2
Shortest Route Problem
2 2
12
7
5 5 9
8
8 7
1 3 3 9
5 6 6
7
6
13
4 4
12
Stage 3
Shortest Route Problem
The general idea for determining the shortest
route is to compute the shortest (cumulative)
distances to all the terminal nodes of a stage and
then use these distances as input data to the
immediately succeeding stage.
13
Shortest Route Problem
Starting from node
1, stage 1 includes
three end nodes, (2, 3,
and 4) and its
computations are:
14
Shortest Route Problem
Stage 1 Summary:
Shortest distance from node 1 to node 2 = 7 miles (from node 1)
15
Shortest Route Problem
Stage 1 Summary:
Shortest distance from node 1 to node 2 = 7 miles (from node 1)
Shortest distance from node 1 to node 3 = 8 miles (from node 1)
16
Shortest Route Problem
Stage 1 Summary:
Shortest distance from node 1 to node 2 = 7 miles (from node 1)
Shortest distance from node 1 to node 3 = 8 miles (from node 1)
Shortest distance from node 1 to node 4 = 5 miles (from node 1)
17
Shortest Route Problem
Next, stage 2 has
two end nodes, 5 and
6. Considering node 5
first:
18
Shortest Route Problem
Stage 2 (node 5):
Shortest Shortest Distance
distance = mini=2,3,4 distance + from node i
to node 5 to node i to node 5
7 + 12 = 19
= min 8 + 8 = 16 = 12 (from node 4)
5 + 7 = 12
19
Shortest Route Problem
Node 6 can be
reached from nodes 3
and 4 only.
20
Shortest Route Problem
Stage 2 (node 6):
Shortest Shortest Distance
distance = mini=3,4 distance + from node i
to node 6 to node i to node 5
8 + 9 = 17
= min = 17 (from node 3)
5 + 13 = 18
21
Shortest Route Problem
Stage 2 Summary:
Shortest distance from node 1 to node 5 = 12 miles (from node 4)
Shortest distance from node 1 to node 6 = 17 miles (from node 3)
22
Shortest Route Problem
The last step is to
consider stage 3. The
destination node 7 can
be reached from either
node 5 or node 6.
23
Shortest Route Problem
Using the summary results from
stage 2 and the distances from
nodes 5 and 6 to node 7, we get:
Stage 3:
Shortest Shortest Distance
distance = mini=5,6 distance + from node i
to node 7 to node i to node 7
12 + 9 = 21
= min = 21 (from node 5) 24
17 + 6 = 23
Shortest Route Problem
Stage 3 Summary:
Shortest distance from node 1 to node 7 = 21 miles (from node 5)
25
Shortest Route Problem
The shortest route is 1 > 4 > 5 > 7 (21 miles).
26
Shortest Route Problem
The example used forward recursion in
which the computations proceed from stage 1 to
stage 3. The same example can be solved by
backward recursion, starting at stage 3 and
ending at stage 1.
27
Shortest Route Problem
Both the forward and backward recursions
yield the same solution. Although the forward
procedure appears more logical, DP literature
invariably uses backward recursion. The reason for
this preference is that, in general, backward
recursion may be more efficient computationally.
28
Shortest Route Problem
The backward recursive equation for shortest-
route problems is:
Where 𝑓4 𝑥4 = 0 for 𝑥4 = 7. The associated
order of computations is 𝑓3 > 𝑓2 > 𝑓1 .
29
Stage 3, i = 3:
d(x3,x4) Optimum Solution
x3
x4 = 7 f3(x3) x4
5 9 9 7
6 6 6 7
30
Stage 2, i = 2:
d(x2,x3) + f3(x3) Optimum Solution
x2
x3 = 5 x3 = 6 f2(x2) x3
2 12 + 9 = 21 - 21 5
3 8 + 9 = 17 9 + 6 = 15 15 6
4 7 + 9 = 16 13 + 6 = 19 16 5 31
Stage 1, i = 1:
d(x1,x2) + f2(x2) Optimum Solution
x1
x2 = 2 x2 = 3 x2 = 4 f1(x1) x2
1 7 + 21 = 28 8 + 15 = 23 5 + 16 = 21 21 4
32
d(x3,x4) Optimum Solution
x3
x4 = 7 f3(x3) x4
5 9 9 7
6 6 6 7
d(x2,x3) + f3(x3) Optimum Solution
x2
x3 = 5 x3 = 6 f2(x2) x3
2 12 + 9 = 21 - 21 5
3 8 + 9 = 17 9 + 6 = 15 15 6
4 7 + 9 = 16 13 + 6 = 19 16 5
d(x1,x2) + f2(x2) Optimum Solution
x1
x2 = 2 x2 = 3 x2 = 4 f1(x1) x2
1 7 + 21 = 28 8 + 15 = 23 5 + 16 = 21 21 4 33
34
