Dynamic programming

See the course in PDF

Dynamic programming is used to solve many problems from operational research, so we will not list tutorials related to this method.

Introduction

Dynamic Programming is an exact method for solving optimization problems, mainly due to R. Bellman (1957). Specifically, dynamic programming is an algorithm design paradigm that can be applied to solve a problem if it has Bellman’s optimality.

Condition for Bellman’s optimalityA problem has the property of optimal substructure if an optimal solution contains the optimal solution of the sub-problems.

progdyn

Dynamic programming is similar to the divide and rule method. The significant difference between these two methods is that dynamic programming allows subproblems to overlap. In other words, a sub-problem can be used in the solution of two different sub-problems. While the divide and conquer approach creates separate subproblems that can be solved independently of one another.

A second difference between these two methods is, as illustrated by the figure above, is that the divide and conquer method is recursive, the recursion takes the global problem to break it into an elementary problem. Dynamic programming is a method whose calculations are done from the bottom up: we start by solving the smaller subproblems. By combining their solution, we get the solutions of sub-problems bigger and bigger.

Principle

The paradigm has four issues:

  1. Characterization of the structure of an optimal solution.
  2. Recursive definition of the value of the optimal solution.
  3. Bottom-up calculation.
  4. Construction of the solution from the ascending calculation.

A table is constructed to memorize the calculations already made: to each element will correspond the solution of one and only one intermediate problem, and one for the final solution. We have to determine the sub-issues to be addressed during the calculation.

There are two approaches to completing the table:

  • Iterative: One initializes the « elements » corresponding to the basic cases.
    We then fill the table according to a very specific order to be determined: we start with the smallest problems of « size », we end with the solution of the main problem: it is necessary that at each calculation, we use only the already calculated solutions.
  • Recursive: The same principle as the iterative approach, this method will only calculate what is strictly necessary to achieve the given objective.

Example : matrix product

Let M1, …, Mbe n matrix , each matrix have  mi rows and mi+1 columns, the inputs are real numbers (linear problem). We want to compute M1*…*Mn with a minimal number of time complexity.

Let cij be the time complexity to compute Mi*…*Mj. Then we have cii=0 and ci(i+1)=m(i-1)*mi*m(i+1). Let’s split this sub-problem by calculating the best cij with Mi*…*Mk andM(k+1)*…*Mj. Then: cij = min [cik + c(k+1)j + mi*m(k+1)*m(j+1)] with k from i to j-1, the last term needs to multiplying the results of the matrix product from i to k with that of k+1 to j.

We have the following program:

  • cij = 0 if i = j;
  • ci(i+1)=m(i-1)*mi*m(i+1);
  • cij = min [cik + c(k+1)j + mi*m(k+1)*m(j+1)] otherwise.

The table of the dynamic program takes as input the number of operations carried out according to the matrices chosen. Take the following example:

i
1
2
3
4
5
6
7
mi
30
35
15
5
10
20
25

The initial table is as follows:

cij
1
2
3
4
5
6
1
0
2
0
3
0
4
0
5
0
6
0

Then we can calculate cij with two matrices (without substructure principle):

cij
1
2
3
4
5
6
1
0
15750
2
0 2625
3
0 750
4
0 1000
5
0 5000
6
0

The rest of the table is diagonally filled following the rule described above:

cij
1
2
3
4
5
6
1
0
15750
7875 9375 11875 15125
2
0 2625 4375 7125 10500
3
0 750 2500 5375
4
0 1000 3500
5
0 5000
6
0

The result is obtained for i = 1 and j = 6, which is the element at the top right of the table. The minimum cost is 15125 operations. A new question arises: how was one proceeded to have a minimum number of calculations?

When we calculate the minimum cost for each box, we choose from two configurations. For example, to calculate c13, we take the minimum between c12*M3 and M1*c23. We note that choice to know the order of calculation of the matrix product.

Kij
1
2
3
4
5
6
1
1 3 3 3
2
3 3 3
3
3 3
4
5
5
6

We read he table as follows: to calculate Mi*Mj, we set k = Kij given by the array and then calculate Mi*…*Mk and M(k+1)*…*Mj.

In our example, to calculate c16, we calculate c13*c46; to calculate c13, we calculate M1*c23; to calculate c46  we calculate c45*M6.

Most algorithms based on dynamic programming remember the choice made for each calculation. Often the result is not important, the path to reach is.

 

Publicités