Dynamic Programming

DynamicProgrammingBellman

In computer science Dynamic Programming is a powerful algorithmic paradigm that can help solve seemingly intractable problems in viable ways.

The rather confusing name ‘Dynamic Programming’ originates from quite an amusing story.
First of all the word ‘Programming’ comes from a time when programmers weren’t programming computers, but were rather planners for logistic purposes (and such).
It is said that Richard Bellman invented the term as some sort of euphemism to avoid pissing off his military boss who hated the word ‘research’ and would turn violent if anyone used it in his presence. So to hide the mathematical character of his work he needed a term that wouldn’t get him into trouble for working on the planning of optimal multi-stage processes, so ‘Dynamic Programming’ it was.

In many algorithmic problems it is common to split a problem down into smaller sub-problems, solve each sub-problem and then re-combine solutions to a full solution for the original problem. The paradigm I just described is commonly referred to as Divide-and-Conquer. The methods to achieve this can vary, but very often some naive form of recursion can be thought out with relative ease. Unfortunately such solutions may lead to an exponential explosion of sub-problems if you allow the recursion to branch.
Certain problems however have the property that generated sub-problems begin to repeat themselves in an overlapping manner. This means the recursive solution does a lot of unnecessary work since it would be possible to avoid re-solving the same problem over and over again if the solution was saved the first time it was encountered and subsequently looked up in a table.

Dynamic Programming algorithms exploit this overlapping property in the way described above to create more efficient solutions.
For these reasons Dynamic Programming solutions can often bring down the runtime of a naive exponential time algorithm to polynomial time. For all practical purposes this can mean the difference between usable and not usable.

A basic example is that of computing the n^{th} term of the Fibonacci sequence.

Problem 1 (Computing The Fibonacci Sequence)

The Fibonacci Sequence is defined via the recursion FIB(n) = FIB(n-1) + FIB(n-2) where FIB(1) = FIB(2) = 1.

The recursive algorithm is straightforward and presented below in pseudo language.

FIB(n)
1. If n \leq 2
2. return(1)
3. Else
4. return( FIB(n-1) + FIB(n-2) )

FibRecpng2

As you can see there are going to be many overlapping subproblems when the recursion tree is expanded.
If we let T(n) represent the number of additions we have to perform to compute FIB(n) we get that T(n) = T(n-1) + T(n-2) + 1. This is a so called non-homogeneous linear difference equation which can be solved for T(n) using methods I outlined in this post (note that so could FIB(n) if we wanted to).
Most importantly however is the realization that T(n) grows exponentially, which can readily be seen from the picture above.

If we save solutions to old subproblems as opposed to recomputing them, it seems like we should be able to bring down the number of additions drastically. Therefore instead of recursively finding a solution top down, we construct a solution bottom up, referring back to smaller sub-problems we solved along the way.
The bottom up approach is generally what characterizes Dynamic Programming algorithms.

Here is pseudo code for a Dynamic Programming solution to the Fibonacci-Recurrence

FIB(n)
1. F[1] \leftarrow 1
2. F[2] \leftarrow 1
3. For i \leftarrow 3 to n
4. F[i] \leftarrow F[i-1] + F[i-2]
5. return( F[n] )

Now our sub-problem graph looks much smaller:

FibDynpng

In fact it is easy to see that only O(n) number of additions are necessary using this algorithm.

Worth noting is that it would have also been possible to pass up solutions to smaller sub-problems in a
top down recursion. This technique is commonly known as memoization (no spelling error).
Each recursive call leaves a ‘memo’ for its parent caller with intermediate results so it can avoid expanding unnecessary branches. The main difference is that memoization is lazy which roughly means it won’t do any evaluation until it must. This can be problematic in practice because of stack depth limits. Dynamic Programming gives you a little bit more freedom as to which order sub-problems should be computed although memoization often feels more “natural” to people which is why some people prefer it.

 

One of the hallmark applications of Dynamic Programming is in solving optimization problems.
The problem should, apart from having overlapping sub-problems also be re-combinable. That is to say, optimal solutions to smaller problems make up optimal solutions to bigger problems. An optimization problem with this property is said to exhibit optimal substructure. These two properties together are pre-requisites for Dynamic Programming solutions.

Problem 2 (Longest and Shortest Paths)

Not all problems exhibit optimal substructure.
Consider the problem of finding the longest simple path in a directed graph with positive weights.

LongestPath

On the other hand the shortest simple path problem in a directed graph with positive weights has got optimal substructure.

ShortestSimplePath

The reason this argument doesn’t work for the Longest Simple Path problem is that concatenating two longest sub-paths may result in loops which are not allowed since paths have to be simple. On the other hand a path that has a loop can never be shortest (removing the loop yields a shorter path).

There are many algorithms for computing shortest paths in a directed graph.
Perhaps among the most well-known is Dijkstra’s Algorithm which only works for graphs with positive weights.
This algorithm exploits the Greedy Choice Property of the problem (which is for a different discussion).
The Dynamic Programming solution works by solving sub-problems of finding the lengths of all shortest paths from a source s to any given node v using at most i intermediate nodes.
The algorithm can also be easily modified to output the actual path by maintaining a successor for every node.

This is what the Dynamic Programming algorithm looks like in pseudo language:

SHORTEST-PATH(G,n,s,d)
1. ForEach node\; v \in V[G]
2. D[v][0] \leftarrow \infty
3. D[s][0] \leftarrow 0
4.
5. For i \leftarrow 1 to n-1\;\; \{
6. ForEach v \in V[G]
7. D[i][v] \leftarrow D[i-1][v]
8. ForEach (v,v') \in E[G]
9. D[i][v] \leftarrow min\{ D[i][v], D[i-1][v] + d(v,v') \}
10. \}
11. return( D )

It’s runtime is O(|V[G]||E[G]|) and its memory requirements O(|V[G]|^2).

There is an improved version of the above code that’s called Bellman-Ford algorithm.
The worst-case runtime complexity of this algorithm is still O(|V[G]||E[G]|) but runs substantially faster in practice. Its memory requirement is reduced to O(|V[G]| + |E[G]| ).
Like the above algorithm it can also handle negative weights as long as there is no negative cycle in the graph.

Also worth mentioning is the Floyd-Warshall algorithm which computes the length of the shortest path between every pair of nodes in a graph. This is also a Dynamic Programming algorithm which successively computes the length of the shortest path between nodes i and j given that the path only uses nodes from \{1,...,k\}.
The input is a weighted n \times n adjacency matrix G.

Floyd-Warshall

FLOYD-WARSHALL(G)
1. n \leftarrow \#Rows[G]
2. For i \leftarrow 1 to n
3. For j \leftarrow 1 to n
4. D[i][j][0] \leftarrow G[i][j]
5.
6. For k \leftarrow 1 to n
7. For i \leftarrow 1 to n
8. For j \leftarrow 1 to n
9. D[i][j][k] \leftarrow min\{ D[i][j][k-1], D[i][k][k-1] + D[k][j][k-1] \}
10.
11. return(\;(D[i][j])[n]\;)

Both runtime and memory are clearly O(n^3) above.
However memory can be reduced to O(n^2) by removing the dimension for k from D (why?)
The algorithm can also be modified to output the shortest paths and not just their length (how?)

 

In the remainder of this post we will look at various other instances of Dynamic Programming problems.

Problem 3 ( The Hiring Problem )

Suppose you are a company manager and have just received an augmented budget to recruit new people into your team to compensate for the increased work load.

The company you work for is popular so there are an abundant number of people applying with all kinds of backgrounds and experience. It is expected that candidates with certain types of profile will provide more ‘value’ (a subjective integer metric) than others, but at the same time eat up more/less of the budget.

You have n different types of profile categories, an array v of the expected value they will provide and an array c of how much they typically cost (in thousands of dollars).
Your additional budget is B thousand dollars and you may choose any number of candidates from each profile category (as long as budget is not breached).

You are tasked to come up with a set of new hires that will provide the most value to the team.

Give an algorithm to compute the optimal hires and their total value added.

Note: This problem is more commonly referred to as the Integer Knapsack Problem with the popular metaphor being what value items a burglar should put in his knapsack if he is only capable of carrying a certain maximum weight.

Solution

The mathematical formulation of this problem can be expressed via the following Integer Program

Integer Knapsack Problem

Maximize \sum \limits_{j=1}^n x_jv[j]

subject to:

\sum \limits_{j=1}^n x_jt[j] \leq B

x_j \geq 0, \;\;\;\;j \in \{ 1,...,n\}

x_j \in \mathbb{Z}, \;\;\;\;j \in \{ 1,...,n\}

 

Let us check first whether this problem even needs a Dynamic Programming solution.
Couldn’t we just be greedy and choose the profiles that maximize value per cost?
The answer is no in general:

GreedyIntegerKnapsack

What about a recursive solution?

REC-KNAPSACK(c,v,B)
1. return( max_j\{ \; c[j] \leq B \; ? \; REC-KNAPSACK(c,v,B-c[j]) + v[j] : 0\;\} )

REC-Knapsack

This algorithm has exponential worst case runtime complexity!

Let’s investigate a Dynamic Programming solution.
What are the sub-problems?

    Define D[k] := Maximum value given budget k

Clearly if the optimal solution to D[k] involves hiring a profile j candidate then removing this hire leaves us with the problem of finding the optimal solution to D[k-c[j]].
Since the optimal hire has to be one of the profiles which can yet fit into the budget we should look for max_j\{  D[k-c[j]] + v[j] : c[j] \leq k \} similarly to how we did for the recursive solution.
However this time we also remember the optimal solutions to the smaller sub-problems.

In a sense if we look at the budgets as nodes and let the costs describe transitions between the nodes weighted by the profile value then this problem is equivalent to finding the longest path in a directed graph with positive weights.
But did we not say earlier that this problem hasn’t got the optimal substructure property?
The difference here is that the graph is acyclic and this eliminates the problem described earlier with concatenation of longest simple sub-paths.
Hence when we are dealing with directed acyclic graphs(DAGs) we do in fact always have optimal sub-structure.
A lot (if not all) Dynamic Programming problems related to optimization can be reduced to the problem of finding the longest/shortest path in a DAG so it is well worth remembering how to solve this problem.

Dyn-Knapsack

Finally we can present the Dynamic Programming algorithm for solving our problem:

INTEGER-KNAPSACK( c,v,B )
1. D[0] \leftarrow 0
2. For k \leftarrow 1 to B
3. D[k] \leftarrow max_j\{  D[k-c[j]] + v[j] : c[j] \leq k \}
4. return(D[B])

To output a team that achieves this maximum you can modify the algorithm as follows:

INTEGER-KNAPSACK'( c,v,B )
1. For k \leftarrow 1 to B\;\;\{
2. D[k] \leftarrow 0
3. For j \leftarrow 1 to n
4. If c[j] \leq k and D[k] < (D[k-c[j]] + v[j])\;\;\{
5. D[k] \leftarrow D[k-c[j]] + v[j]
6. T[k] \leftarrow j
7. \}
8. \}
9. return(T)

Then you can follow pointers back and unfold the optimal solution via T[B], T[B - T[B]], T[B - (T[B]+T[B-T[B]])],....

The algorithm has runtime complexity O(nB) and O(B) memory requirements.

Is that really good?
Well it is better than exponential, but the runtime is unfortunately dependent on the value of the input rather than just the size of it. For that reason we say that the complexity is pseudo-polynomial.
For general B this problem is actually NP-hard.

 
 

Now let’s look at a slightly trickier problem.

Problem 4 (The Firing Problem)

This time you are also managing a team but the company you are working for is not doing very well so they need you to fire people in order to maintain a tighter budget for your team.

Given are n people in your team with values v and costs c.

Your new budget is B thousand dollars.

Give an algorithm for computing the set of people you should keep in order to maximize value while not breaching budget.

FiringProblem

Note: This problem is more commonly referred to as the Binary Knapsack Problem

Solution

This problem looks awfully similar to the previous problem.
There is however one important difference.
You can only keep or fire a person once!

The corresponding integer program is given by

Binary Knapsack Problem

Maximize \sum \limits_{j=1}^n x_jv[j]

subject to:

\sum \limits_{j=1}^n x_jt[j] \leq T

x_j \in \{ 0,1 \}, \;\;\;\;j \in \{ 1,...,n\}

 

In the previous problem we were able to define sub-problems as

    D[k] := Maximum value given budget k

Here this doesn’t work, how do we know if we have already kept an employee or not?
If we have, we cannot keep the employee twice so it seems we need to enlarge our state space to take this into account.

We can make the following new definition:

    D[k][j] := Maximum value given budget k using only employees from \{ 1,...,j \}

When we increment the second parameter we have the value of the optimal team using one less employee for the same budget. The new employee either is, or is not part of an optimal team with the given budget.
Whichever it is this employee must be added to a team which is optimal with respect to the other employees before it.
So with a budget of k we can either gain or not gain by adding employee j to the optimal solution for D[k-c[j]][j-1] over not adding employee j to the optimal team using only employees in \{ 1,...,j-1 \}.

We thus get the following expression for the optimal value of a subproblem:

    D[k][j] := max\{ D[k-c[j]][j-1] + v[j], D[k][j-1] \}

Hence we can construct the following Dynamic Programming algorithm:

BINARY-KNAPSACK(c,v,B)
1. For k \leftarrow 1 to B
2. D[k][0] \leftarrow 0
3. For j \leftarrow 1 to n
4. D[0][j] \leftarrow 0
5.
6. For k \leftarrow 1 to B
7. For j \leftarrow 1 to n\;\;\;\{
8. T[k][j] \leftarrow 0
9. If c[j] \leq k and (D[k-c[j]][j-1] + v[j]) > D[k][j-1] \;\;\{
10. D[k][j] \leftarrow D[k-c[j]][j-1] + v[j]
11. T[k][j] \leftarrow 1
12. \}
13. Else
14. D[k][j] \leftarrow D[k][j-1]
15. \}
16. return( T[B] )

The optimal team is then found by iterating over T[B] firing every employee j such that T[B][j] = 0 and keeping the rest (hopefully there are no bugs).

The algorithm has runtime complexity O(nB) and O(nB) memory requirements.

 

The time management problem where n tasks are given taking t[j] hours to complete and have value v[j] for j = 1,...,n is also equivalent to the Binary Knapsack problem. The knapsack capacity is given by a global deadline T and the problem is to pick out the tasks that will maximize value before hitting deadline. In general any problem which fits the integer program specification can be solved using the same algorithm.

The final problem along with its many variations is a very intriguing problem which occurs naturally in many real-world situations. Unfortunately its general formulation is very hard to solve (NP-hard in fact).
However if we make some simplifying assumptions it can be solved optimally in polynomial time using a Dynamic Programming approach (though still very unpractical for larger inputs).

Problem 5 (The Parallel Task Scheduling Problem)

Given are n tasks of k different types with multiplicities m[j] and processing times t[j] for 1 \leq j \leq k

You have a requirement that all tasks need to finish before time T.

To achieve this the tasks need to be scheduled to run in parallel on a number of identical machines.

Give an algorithm for computing the minimum number of machines needed.

Solution

This problem is a restricted version of the general 1-dimensional Bin Packing Problem.
In the bin-packing problem the assumption that there can only exist k different item-types is relaxed to allow for any number of item sizes.

This problem can be specified via the following integer program:

Restricted Bin Packing Problem

Minimize \sum \limits_{i=1}^n y_i

subject to:

\sum \limits_{j=1}^k \sum \limits_{l=1}^{m[j]} t[j]x_{_{i},_{f(j,l)}} \leq y_iT,\;\;\;\;i \in \{ 1,...,n\}

f(j,l) = l + \sum \limits_{r=1}^{j-1} m[r]

\sum \limits_{i=1}^n x_{i,j} = 1, \;\;\;\;j \in \{ 1,...,n\}

y_i \in \{ 0,1 \}, \;\;\;\;i \in \{ 1,...,n\}

x_{i,j} \in \{ 0,1 \}, \;\;\;\;i \in \{ 1,...,n\},\;j \in \{ 1,...,n\}

 

Here x_{i,j} = 1 if task j is scheduled for machine i and y_i = 1 if machine i is used.
The first constraint says that the processing time for all tasks scheduled on machine i should not exceed T and the third constraint that each task is scheduled on exactly one machine.

It is quite clear that a naive brute-force solution to this problem is intractable.
Effectively we would have to enumerate all partitions of n tasks (of which there are exponentially many), check that none of the subsets of the partition exceed the time limit (in linear time) and then take the minimum over all such feasible partitions.

What about a Dynamic Programming solution?

A natural choice for our sub-problems are

    D[j_1]...[j_k] = Minimal number of machines needed with j_r tasks of type r

The tricky part is how we should transition from smaller to larger problem instances.
We cannot simply remove a task and ask what the optimal solution is to the sub-problem since the number of required machines could either increase or remain the same through some potential rearrangement, so there is no obvious way to build on top of a smaller optimal solution with a single new task.

The easiest way to get to a bigger instance from a smaller one is by stepping one machine at a time i.e if we know all possible ways of combining tasks into a single machine then the optimal solution to D[j_1]...[j_k] is obtained from the optimal solution to D[j_1-a_1]...[j_k-a_k] by considering all possible task tuples (a_1,...,a_k) s.t a_1t[1]+...+a_kt[k] \leq T fitting into one machine.
So an optimal solution can be obtained by stepping forward with one machine from some optimal solution with one less machine whichever way it may be, we must consider all tuples that could possibly be assigned to that machine since any of the extensions could be optimal.

BinPackingSolution

Define the set A := \{ (a_1,...,a_k) \in \mathbb{Z}^k: a_1t[1]+...+a_kt[k] \leq T, 0 \leq a_i \leq m[i], i = 1,...,k  \} of all ways of filling one machine with tasks satisfying the constraint T. Then A has size at most O(n^k)

We can compute A in O(n^k) time via the following algorithm (which if implemented properly should rather be recursively defined with a parameter k)

INITIALIZE(t,m,k,T)
1. A \leftarrow \emptyset
2. For a_1 \leftarrow 0 to m[1]
3. For a_2 \leftarrow 0 to m[2]
4.
5. For a_k \leftarrow 0 to m[k]
6. If a_1t[1]+...+a_kt[k] \leq T\;\;\;\{
7. A \leftarrow A \bigcup \{(a_1,...,a_k)\}
8. D[a_1]...[a_k] \leftarrow 1
9. \}
10. return(A,D)

We can now compute the minimum number of required machines via:

RESTRICTED-BIN-PACKING(t,m,k,T)
1. (A,D) \leftarrow INITIALIZE(t,m,k,T)
2. D[0]...[0] \leftarrow 0
3. For j_1 \leftarrow 0 to m[1]
4. For j_2 \leftarrow 0 to m[2]
5.
6. For j_k \leftarrow 0 to m[k]
7. D[j_1]...[j_k] \leftarrow \min \limits_{(a_1,...,a_k) \in A} \{ 1 + D[j_1-a_1]...[j_k-a_k] : j_i \geq a_i, i=1,...,k \}
8. return(D[m[1]]...[m[k]])

For each of the at most O(n^k) sub-problems we do at most O(n^k) work by computing the min over all base configurations. Hence worst-case runtime complexity is O(n^{2k}) i.e polynomial in the size of the task input for fixed k. Space requirement is O(n^k).

 

The bin packing problem arises naturally in many logistics problems such as the problem of finding the minimum number of lorries required to deliver goods of different sizes or the minimum number of shelves needed in a storage room. It also arises in advertisement problems, where you for instance want to fit a certain number of commercials of different length in a minimum series of 3 minute television breaks. As we have seen above it can also arise in scheduling problems. Wikipedia mentions another interesting variant of the Bin Packing problem where items could occupy less space in comparison to the sum of their individual sizes when packed together. This arises in the problem of minimizing physical servers hosting virtual machines (VMs), where resource sharing may occur on the host. For that reason this variation of the problem is referred to as VM packing.
Needless to say the Bin Packing problem is very important.

Many other nice variations of this problem also exists. For example one may be interested in looking at bins of multiple capacities, higher dimensional extensions of the bins/items, different geometrical shapes of the bins/items or looking at online versions of these problems (i.e where items arrive incrementally) and etc…

We saw that the Bin Packing problem admitted a polynomial time solution when restricted to k distinct types of items. The performance however is still rather dreadful in practice. Often when dealing with difficult problems such as the Bin Packing problem one has to resort to heuristics and approximation algorithms.

One simple such heuristic is the Next-Fit packing algorithm which traverses the items once and checks whether the next item fits in the last bin. If it does, then it puts it there, if it doesn’t then it opens a new bin. This may seem like a rather crude way of going about it, but the algorithm has certain advantages.
For instance it is only linear time, works online and outputs at most twice the optimal number of bins [Exercise 1].

First-Fitpng

Yet another simple heuristic which is slightly slower [O(n^2) or less depending on implementation] but gives better results is the First-Fit packing algorithm. This algorithm repeatedly traverses the list of items and inserts into the last bin the first item that fits into it. If no item fits, it opens a new bin and goes through the list again until all items are gone.

……

This concludes our discussion about dynamic programming.
There are many other interesting problems which fit this topic. You will see two of them in the exercises below, but I recommend signing up to places like TopCoder and check out their practice rooms for a large variety of other Dynamic Programming problems of varying difficulty.
If you are interested in algorithms in general you may also find it worthwhile to check out Wikipedia’s list of algorithms.
The standard book carried around by all computer scientists you can find here.

 
 

Exercise 1 (Next-Fit Bin Packing – Easy):

Prove that the Next-Fit bin packing algorithm never does worse than two times the number of bins in the optimal solution.

 

Exercise 2 (Maximum Sum Contiguous Subsequence – Easy):

Give an O(n) algorithm for finding the value of the maximum sum contiguous subsequence in an array of integers.

[Think carefully about what the sub-problems should be in a Dynamic Programming solution and how you would transition between them]

 

Exercise 3 ( Which Meetings To Attend? – Intermediate):

Your day is very busy and your calendar is packed with meetings and various other commitments (all here referred to as “meetings”), some possibly overlapping.

You are given an array s of starting times for each meeting, an array f of corresponding finishing times and an array w of corresponding importance of the meetings.

Since you can only attend one meeting at a time you wish to pick out a subset of non-overlapping meetings which maximizes the total importance.

Give a Dynamic Programming algorithm for computing the optimal meeting schedule.

(Hint: You may wish to do some pre-processing to compute an array which gives you the latest finishing meeting not overlapping with meeting j)

Example:

SchedulingDP

 

Advertisements
This entry was posted in Algorithms, Uncategorized and tagged , , , , , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s