Dynamic programming

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.

Example: the coin changing problem

Suppose we need to make change for 67£. We want to do this using the fewest number of coins possible among: 1, 5, 10, 25.

If the following coins are available: 1, 5, 10, 25. It is easy to see the optimal solution 67=2*25+10+5+2*1. By repeatedly choosing the largest coin less than or equal to the remaining sum, the desired sum is obtained by a greedy algorithm.

The formal description of the Coin Changing problem is as follows: Let D={ d1,..,dk} be a finite set of distinct coin denominations. We assume each di is an integer and the set is in increasing order. Each denomination is available in unlimited quantity. The problem is to make change for n£ using a minimum total number of coins, dk =1 so there is always a solution.

The greedy method does not work in any case (it does not give an optimal solution). For example, D={25,10,1} and n=30. The greedy method would produce a solution: 25+5*1, which is not as good as 3*10.

Step 1: Characterize the substructure. Define C[j] to be the minimum number of coins we need to make change for j£. If we knew that an optimal solution for the problem of making change for j£ used a coin of denomination  we would have C[j]=1+C[j-di].

Step 2: Define the value of an optimal solution. We can recursively define the value of an optimal solution from the equation found in step 1.

dynprog

Step 3: Algorithm.

Coin-Changing(n,d,k)
C[0]=0;
For j from 1 to n
     C[j]=inf;
     For i from 1 to k
          If j>=di and C[j-di]<C[j] then
               C[j]=1+C[j-di]
               Denom[j]=di
Return C

 

We use an additional array Denom, where Denom[j] is the denomination of a coin used in an optimal solution to the problem of making change for j£. If the following coins are available: 1, 5, 10, 25:

j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
C[j] 0 1 2 3 4 1 2 3 4 5 1 2 3 4 5 2
Denom[j] 0 1 1 1 1 5 1 1 1 1 10 1 1 1 1 5

Given some n£, find all the combinations of coins that make up the value, the following coins are available: 1, 5, 10, 25. For example, for N=4, D={1,2,3} there are four solutions: {1,1,1,1}, {1,1,2}, {2,2} and {1,3}.

Step 1: The set of solutions for this problem,  C(N,m) can be partitioned into two sets:

  1. There are those sets that do not contain any dm
  2. Those sets that contain at least 1 dm

If a solution does not contain dm, then we can solve the subproblem of N with D={d1, ..,dm-1}, or the solutions of C(N,m-1).

If a solution does contain dm, then we are using at least one dm, thus we are now solving the subproblem of  N- dm , with D={d1, ..,dm}. This is C(N- dm, m).

Step 2: Thus, we can formulate the following: C(N-m)=+ C(N- dm, m) with the base cases:

  • C(N,m)=1, N=0
  • C(N,m)=0, N<0 (negative sum of money)
  • C(N,m)=0, N>=1, m<=0 (no change available).

Step 3: The algorithm is as follows:

 

n/d 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4
10 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6
25 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6

 

Publicités