Dynamic Programming for Solving

Optimization Problems

(Chain Matrix Multiplication Problem)

Optimizations problem?
Steps in Development of Dynamic Algorithms
Why dynamic in optimization problem?
Introduction to Catalan numbers
Chain-Matrix Multiplication
Problem Analysis
 Brute Force approach
 Time Complexity

Conclusion
 Optimization Problems

•If a problem has only one correct solution, then

optimization is not required
•For example, there is only one sorted sequence
containing a given set of numbers.
•Optimization problems have many solutions.
•We want to compute an optimal solution e. g. with
minimal cost and maximal gain.
•There could be many solutions having optimal value
•Dynamic programming is very effective technique
•Development of dynamic programming algorithms can
be broken into a sequence steps as in the next.
 Steps in Development of Dynamic Algorithms

1. Characterize the structure of an optimal solution

2. Recursively define the value of an optimal
solution
3. Compute the value of an optimal solution in a
bottom-up fashion
4. Construct an optimal solution from computed
information
Note: Steps 1-3 form the basis of a dynamic
programming solution to a problem. Step 4 can
be omitted only if the value of an optimal solution
is required.
 Why Dynamic Programming?

Dynamic programming, like divide and conquer

method, solves problems by combining the solutions to
sub-problems.
Divide and conquer algorithms:
•partition the problem into independent sub-problem
•Solve the sub-problem recursively and
•Combine their solutions to solve the original problem
In contrast, dynamic programming is applicable
when the sub-problems are not independent.
Dynamic programming is typically applied to
optimization problems.
 Time Complexity in Dynamic Algorithms

Time complexity:
 If there are polynomial number of sub-problems.
 If each sub-problem can be computed in polynomial time.
 Then the solution of whole problem can be found in polynomial time.

Remark:
Greedy also applies a top-down strategy but usually on one sub-problem
so that the order of computation is clear
 Time Complexity in Dynamic Algorithms

Polynomial Time
•An algorithm is said to be solvable in polynomial
time if the number of steps required to complete
the algorithm for a given input is O(n^k) for some
nonnegative integer k, where n is the complexity
of the input.
•Polynomial-time algorithms are said to be "fast.“
•Most familiar mathematical operations such as
addition, subtraction, multiplication, and division,
as well as computing square roots, powers, and
logarithms, can be performed in polynomial time.
CATALAN NUMBERS
 Multiplying n Numbers

Objective: n multiplication order

Find C(n), the number of 2 (x1 · x2)
ways to compute product 3 (x1 · (x2 · x3))
x1 . x2 …. xn. ((x1 · x2) · x3)
4 (x1 · (x2 · (x3 · x4)))
(x1 · ((x2 · x3) · x4))
((x1 · x2) · (x3 · x4))
((x1 · (x2 · x3)) · x4)
(((x1 · x2) · x3) · x4)
Multiplying n Numbers – small n

n C(n)
1 1
2 1
3 2
4 5
5 14
6 42
7 132
 Multiplying n Numbers - small n
Recursive equation:
where is the last multiplication?
n −1
C ( n) =  C (k )  C (n − k )
k =1
1  2n − 2 
Catalan numbers: C (n) =  .
n  n −1 

4n
Asymptotic value: C ( n)  3 / 2
n
C(n)
→ 4 for n → 
C(n - 1)
CHAIN-MATRIX MULTIPLICATION
Problem Statement: Chain Matrix Multiplication

Statement: The chain-matrix multiplication problem can

be stated as below:
Given a chain of [A1, A2, . . . , An] of n matrices where
for i = 1, 2, . . . , n, matrix Ai has dimension pi-1 x pi,
find the order of multiplication which minimizes the
number of scalar multiplications.
Note:
Order of A1 is p0 x p1,
Order of A2 is p1 x p2,
Order of A3 is p2 x p3, etc.
Order of A1 x A2 x A3 is p0 x p3,
Order of A1 x A2 x . . . x An is p0 x pn
 Objective is to find order not multiplication

Given a sequence of matrices, we want to find a most

efficient way to multiply these matrices
It means that problem is not actually to perform the
multiplications, but decide the order in which these must
be multiplied to reduce the cost.
This problem is an optimization type which can be solved
using dynamic programming.
The problem is not limited to find an efficient way of
multiplication of matrices, but can be used to be applied
in various purposes.
But how to transform the original problem into chain
matrix multiplication, this is another issue, which is common
in systems modeling.
Why this problem is of Optimization Category?

If these matrices are all square and of same size, the

multiplication order will not affect the total cost.
If matrices are of different sizes but compatible for
multiplication, then order can make big difference.
Brute Force approach
The number of possible multiplication orders are
exponential in n, and so trying all possible orders may
take a very long time.
Dynamic Programming
To find an optimal solution, we will discuss it using
dynamic programming to solve it efficiently.
 Assumptions (Only Multiplications Considered)

We really want is the minimum cost to multiply

But we know that cost of an algorithm depends on how
many number of operations are performed i.e.
We must be interested to minimize number of operations,
needed to multiply out the matrices.
As in matrices multiplication, there will be addition as well
multiplication operations in addition to other
Since cost of multiplication is dominated over addition
therefore we will minimize the number of multiplication
operations in this problem.
In case of two matrices, there is only one way to multiply
them, so the cost fixed.
Chain Matrix Multiplication
(Brute Force Approach)
Brute Force Chain Matrix Multiplication Algorithm
If we wish to multiply two matrices:
A = a[i, j]p, q and B = b[i, j]q, r
Now if C = AB then order of C is p x r.
Since in each entry c[i, j], there are q number of
scalar of multiplications
Total number of scalar multiplications in
computing C = Total entries in C x Cost of
computing a single entry = p . r . q
Hence the computational cost of AB = p . q . r
The formula to calculate single entry.
 Brute Force Chain Matrix Multiplication

Example
Given a sequence [A1, A2, A3, A4]
Order of A1 = 10 x 100
Order of A2 = 100 x 5
Order of A3 = 5x 50
Order of A4 = 50x 20

Compute the order of the product A1 . A2 . A3 . A4 in such

a way that minimizes the total number of scalar
multiplications.
 Brute Force Chain Matrix Multiplication

There are five ways to parenthesize this product

Cost of computing the matrix product may vary,
depending on order of parenthesis.
All possible ways of parenthesizing

(A1 · (A2 . (A3 . A4)))

(A1 · ((A2 . A3). A4))
((A1 · A2). (A3 . A4))
((A1 · (A2 . A3)). A4)
(((A1 · A2). A3). A4)
 Kinds of problems solved by algorithms

1 10 x 100 x 20 = 20000
10 x 20
A1 2 100 x 5 x 20 = 10000
10 x 100

100 x 20
3 5 x 50 x 20 = 5000
A2
100 x 5
5 x 20 Total Cost = 35000
A3 A4
5 x 50 50 x 20
 Second Chain : (A1 · ((A2 . A3). A4))

1
10 x100 x 20 = 20000
10 x 20

3
A1 100 x 50 x 20 = 100000
10 x 100

2 100 x 20
A4 100 x 5 x 50 = 25000
50 x 20
100 x 50
Total Cost = 145000
A2 A3
100 x 5 5 x 50
 Third Chain : ((A1 · A2). (A3 . A4))

10 x 5 x 20 = 1000
2

10x20
10 x 100 x 5 = 5000 5 x 50 x 20 = 5000
1
3
10 x 5 5 x 20

A1 A2 A3 A4
10 x 100 100 x 5 5 x 50 50 x 20

Total Cost = 11000

 Fourth Chain : ((A1 · (A2 . A3)). A4)

3
10 x 50 x 20 = 10000
10x20

10 x 100 x 50 = 50000
1 A4
50x20

100 x 5 x 50 = 25000 10x50

A1 2
Total Cost = 85000 10x100

100x50
A3
A2
5x50
100x5
 Fifth Chain : (((A1 · A2). A3). A4)
10 x 50 x 20 = 10000 3
10 x 20

10 x 5 x 50 = 2500 2 A4
50 x 20
10 x 50

10 x 100 x 5 = 5000
1 A3
5 x 50
Total Cost = 17500
10 x 5

A1 A2
10 x 100 100 x 5
 Chain Matrix Cost

First Chain 35,000

Second Chain 145,000
((A1 · A2). (A3 . A4))
Third Chain 11,000
Fourth Chain 85,000 2

Fifth Chain 17,500 10x20

1
3
10 x 5 5 x 20

A1 A2 A3 A4
10 x 100 100 x 5 5 x 50 50 x 20
 Generalization of Brute Force Approach
If there is sequence of n matrices, [A1, A2, . . . , An]
Ai has dimension pi-1 x pi, where for i = 1, 2, . . . , n
Find order of multiplication that minimizes number of
scalar multiplications using brute force approach
Recurrence Relation: After kth matrix, create two sub-lists, one
with k and other with n - k matrices i.e.
(A1 A2A3A4A5 . . . Ak) (Ak+1Ak+2…An)
Let P(n) be the number of different ways of
parenthesizing n items
 Generalization of Brute Force Approach
If n = 2
P(2) = P(1).P(1) = 1.1 = 1
If n = 3
P(3) = P(1).P(2) + P(2).P(1) = 1.1 + 1.1 = 2
(A1 A2A3) = ((A1 . A2). A3) OR (A1 . (A2. A3))
If n = 4
P(4) = P(1).P(3) + P(2).P(2) + P(3).P(1) = 1.2 + 1.1 + 2.1
=5
 Why Brute Force Approach not Economical

This is related to a famous function in combinatorics

called the Catalan numbers.
Catalan numbers are related with the number of
different binary trees on n nodes.
P(n)  (4n/n3/2)
The dominating term is the exponential 4n thus P(n) will
grow large very quickly.
And hence this approach is not economical.
Problem Statement: Chain Matrix Multiplication
Statement: The chain-matrix multiplication problem
can be stated as below:
Given a chain of [A1, A2, . . . , An] of n matrices for i =
1, 2, . . . , n, matrix Ai has dimension pi-1 x pi, find the
order of multiplication which minimizes the number of
scalar multiplications.
Note:
Order of A1 is p0 x p1,
Order of A2 is p1 x p2,
Order of A3 is p2 x p3, etc.
Order of A1 x A2 x A3 is p0 x p3,
of A1 x A2 x . . . x An is p0 x pn
Dynamic Programming Solution
Why Dynamic Programming in this problem?

•Problem is of type optimization

•Sub-problems are dependent
•Optimal structure can be characterized and
•Can be defined recursively
•Solution for base cases exits
•Optimal solution can be constructed
•Hence here is dynamic programming
 Dynamic Programming Formulation

•Let Ai..j = Ai . Ai+1 . . . Aj

•Order of Ai = pi-1 x pi, and
•Order of Aj = pj-1 x pj,
•Order of Ai..j = rows in Ai x columns in Aj = pi-1 × pj
•At the highest level of parenthesisation,
• Ai..j = Ai..k × Ak+1..j i≤k<j
•Let m[i, j] = minimum number of multiplications needed to
compute Ai..j, for 1 ≤ i ≤ j ≤ n
•Objective function = finding minimum number of
multiplications needed to compute A1..n
i.e. to compute m[1, n]
 Mathematical Model
Ai..j = (Ai. Ai+1….. Ak). (Ak+1. Ak+2….. Aj) = Ai..k × Ak+1..j
i≤k<j
Order of Ai..k = pi-1 x pk, and order of Ak+1..j = pk x pj,
m[i, k] = minimum number of multiplications needed to
compute Ai..k
m[k+1, j] = minimum number of multiplications needed
to compute Ak+1..j
Mathematical Model
 Example: Dynamic Programming

Problem: Compute optimal multiplication order for a

series of matrices given below

A1 A2 A3 A4
. . .
10 100 100  5 5  50 50  20

P0 = 10 m[1,1] m[1,2] m[1,3] m[1,4]

P1 = 100 m[2,2] m[2,3] m[2,4]
P2 = 5 m[3,3] m[3,4]
P3 = 50 m[4,4]
P4 = 20
 Main Diagonal

m[i, i ] = 0, i = 1,...,4
m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )
ik  j

Main Diagonal
m[1, 1] = 0
m[2, 2] = 0
m[3, 3] = 0
m[4, 4] = 0
 Computing m[1, 2], m[2, 3], m[3, 4]

m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )

ik  j

m[1,2] = min (m[1, k ] + m[k + 1,2] + p0 . pk . p2 )

1 k  2

m[1,2] = min (m[1,1] + m[2,2] + p0 . p1. p2 )

m[1, 2] = 0 + 0 + 10 . 100 . 5
= 5000
s[1, 2] = k = 1
 Computing m[2, 3]

m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )

ik  j

m[2,3] = min (m[2, k ] + m[k + 1,3] + p1. pk . p3 )

2 k 3

m[2,3] = min (m[2,2] + m[3,3] + p1. p2 . p3)

m[2, 3] = 0 + 0 + 100 . 5 . 50
= 25000
s[2, 3] = k = 2
 Computing m[3, 4]

m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )

ik  j

m[3,4] = min (m[3, k ] + m[k + 1,4] + p2 . pk . p4 )

3 k  4

m[3,4] = min (m[3,3] + m[4,4] + p2 . p3 . p4 )

m[3, 4] = 0 + 0 + 5 . 50 . 20
= 5000
s[3, 4] = k = 3
 Computing m[1, 3], m[2, 4]

m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )

ik  j

m[1,3] = min (m[1, k ] + m[k + 1,3] + p0 . pk . p3 )

1 k 3

m[1,3] = min (m[1,1] + m[2,3] + p0 . p1. p3 ,

m[1,2] + m[3,3] + p0 . p2 . p3 ))
m[1, 3] = min(0+25000+10.100.50, 5000+0+10.5.50)
= min(75000, 2500) = 2500
s[1, 3] = k = 2
 Computing m[2, 4]

m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )

ik  j

m[2,4] = min (m[2, k ] + m[k + 1,4] + p1. pk . p4 )

2 k  4

m[2,4] = min (m[2,2] + m[3,4] + p1. p2 . p4 ,

m[2,3] + m[4,4] + p1. p3 . p4 ))

m[2, 4] = min(0+5000+100.5.20, 25000+0+100.50.20)
= min(15000, 35000) = 15000
s[2, 4] = k = 2
 Computing m[1, 4]
m[i, j ] = min (m[i, k ] + m[k + 1, j ] + pi −1. pk . p j )
ik  j

m[1,4] = min (m[1, k ] + m[k + 1,4] + p0 . pk . p4 )

1 k  4

m[1,4] = min (m[1,1] + m[2,4] + p0 . p1. p4 ,

m[1,2] + m[3,4] + p0 . p2 . p4 , m[1,3] + m[4,4] + p0 . p3 . p4 )

m[1, 4] = min(0+15000+10.100.20, 5000+5000+
10.5.20, 2500+0+10.50.20)
= min(35000, 11000, 35000) = 11000
s[1, 4] = k = 2
 Final Cost Matrix and Its Order of Computation

Final Cost Matrix 0 5000 2500 11000

0 25000 15000
0 5000
0

1 5 8 10
2 6 9
Order of Computation 3 7
4
K,s Values Leading Minimum m[i, j]

0 1 2 2
0 2 2
0 3
0
 Representing Order using Binary Tree
The above computation shows that the minimum cost for
multiplying those four matrices is 11000.
The optimal order for multiplication is
((A1 . A2) . (A3 . A4))
2
For, m(1, 4) 10x20
k=2 1
3
10 x 5 5 x 20

A1 A2 A3 A4
10 x 100 100 x 5 5 x 50 50 x 20
 Chain-Matrix-Order(p)
1. n  length[p] – 1
2. for i  1 to n m[1,1] m[1,2] m[1,3] m[1,4]
3. do m[i, i]  0 m[2,2] m[2,3] m[2,4]
4. for l  2 to n, m[3,3] m[3,4]
5. do for i  1 to n-l+1 m[4,4]
6. do j  i+l-1
7. m[i, j]  
8. for k  i to j-1
9. do q  m[i, k] + m[k+1, j] + pi-1 . pk . pj
10. if q < m[i, j]
11. then m[i, j] = q
12. s[i, j]  k
 Computational Cost
n n n n −i
T (n) = n +   ( j − i ) =  k
i =1 j =i +1 i =1 k =1

n
(n − i )(n − i + 1)
T ( n) = n + 
i =1 2
1 n 2
T (n) = n +  (n − 2ni + i 2 + n − i)
2 i =1
1 n 2 n n n n
T (n) = n + ( n −  2ni +  i 2 +  n −  i)
2 i =1 i =1 i =1 i =1 i =1
 Computational Cost

1 n 2 n n n n
T (n) = n + ( n −  2ni +  i 2 +  n −  i)
2 i =1 i =1 i =1 i =1 i =1

1 2 n n n n n
T ( n) = n + ( n 1 − 2n  i +  i 2 + n 1 −  i )
2 i =1 i =1 i =1 i =1 i =1

1 2 n(n + 1) n(n + 1)(2n + 1) n(n + 1)

T (n) = n + (n .n − 2n. + + n.n − )
2 2 6 2
 Computational Cost

1 2 n(n + 1) n(n + 1)(2n + 1) n(n + 1)

T (n) = n + (n .n − 2n. + + n.n − )
2 2 6 2

1 3 n(n + 1)(2n + 1) n(n + 1)

T (n) = n + (n − n (n + 1) +
2
+n −
2
)
2 6 2

1
T (n) = n + (6n3 − 6n3 − 6n 2 + 2n3 + 3n 2 + n + 6n 2 − 3n 2 − 3n)
12

1 1 1
T (n) = (12n + 2n − 2n) = (10n + 2n ) = (5n + n3 )
3 3

12 12 6
Cost Comparison Brute Force Dynamic Programming

Dynamic Programming
There are three loop
The most two loop for i, j, satisfy the condition: 1
i j n
Cost = nC2 + n = n(n-1)/2 + n =  (n2)
The third one most inner loop for k satisfies the
condition, i k < j, in worst case, it cost n and
Hence total cost =  (n2 . n) =  (n3)
Brute Force Approach
P(n) = C(n - 1) C(n)  (4n/n3/2)
 Generalization: Sequence of Objects

Although this algorithm applies well to the problem of

matrix chain multiplication
Many researchers have noted that it generalizes well to
solving a more abstract problem
• given a linear sequence of objects
• an associative binary operation on those objects hold
• the objective to find a way to compute the cost of performing
that operation on any two given objects
• and finally computing the minimum cost for grouping these
objects to apply the operation over the entire sequence.
It is obvious that this problem can be solved using chain
matrix multiplication, because there is a one to one
correspondence between both problem
 Generalization: String Concatenation

One common special case of chain matrix multiplication

problem is string concatenation.
For example, we are give a list of strings.
•The cost of concatenating two strings of length m and n is
for example O(m + n)
•Since we need O(m) time to find the end of the first string
and O(n) time to copy the second string onto the end of it.
•Using this cost function, we can write a dynamic
programming algorithm to find the fastest way to
concatenate a sequence of strings
•It is possible to concatenate all in time proportional to sum
of their lengths, but here we are interested to link this
problem with chain matrix multiplication
 Generalization: Parallel Processors

Another generalization is to solve the problem when

many parallel processors are available.
In this case, instead of adding the costs of computing
each subsequence, we just take the maximum, because
we can do them both simultaneously.
This can drastically affect both the minimum cost and
the final optimal grouping
But of course more balanced groupings that keep all
the processors busy is more favorable solution
There exists some more sophisticated approaches to
solve this problem
 Conclusion

Created some notations to describe mathematical

model of the chain matrix multiplication problem
A recursive model was described
Based on this model dynamic programming
algorithm was designed
An example was taken for applying model to solve
dynamically, constructing optimal solution based on
the given information
Time complexity was computed for the Algorithm
Applications of chain matrix problem are discussed