Skip to content

Principles of dynamic programming

Part 3 · Dynamic programming · Chapter 16 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Principles

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • explain why enumerating all the feasible solutions fails, and what a DP algorithm does instead;

  • state the divide, conquer and combine principles, and the difference between independent subproblems and overlapping subproblems;

  • check the optimal substructure and the overlapping subproblems on a problem;

  • list the steps of a DP algorithm: recurrence, base cases, lookup table, and reconstruction of an optimal solution.

16.1 Divide, conquer and combine

Definition 16.1: DP algorithm

A Dynamic Programming (DP) algorithm is an exact algorithm to find an optimal solution of a class of optimization problems with specific properties (Section 16.2). It decomposes the original problem into smaller subproblems of the same type, and it reuses the information computed when solving them.

  • A brute-force algorithm lists all the feasible solutions, and their number grows exponentially (\(2^n\) subsets of items for the KP). A DP algorithm avoids this enumeration by reusing the optimal values of the subproblems.

  • A DP algorithm exploits the divide, conquer, and combine paradigm, whose main principles are:

    1. Dividing principle \(\rightsquigarrow\) decompose the problem into a number of subproblems that are smaller problems of the same type;

    2. Conquering principle \(\rightsquigarrow\) solve the subproblems in a recursive manner. If the subproblem sizes are small enough just solve the subproblems in a straightforward manner;

    3. Combining principle \(\rightsquigarrow\) combine optimal solutions of the subproblems to obtain an optimal solution for the original problem.

  • DP algorithms divide the problem into independent subproblems, solve them recursively, and then combine their solutions to solve the original problem. Here, independent means that each subproblem generated by the division can be solved without affecting the others.

  • In a DP algorithm, the same subproblem may be generated several times during the recursive solution process. In order to avoid redundant computations, the optimal value of each subproblem is stored in a lookup table.

  • Whenever the same subproblem is generated again, its optimal value is retrieved from the lookup table instead of being recomputed.

16.2 Problem properties required by DP algorithms

  • DP algorithms work only for combinatorial optimization problems that allow a recursive decomposition process respecting the following properties:

    1. Optimal Substructure \(\rightsquigarrow\) the idea is that, when a problem is decomposed into smaller subproblems, an optimal solution of the problem can be built from optimal solutions of the subproblems.

      In practice, to verify this property one usually checks the following points:

      • the problem can be decomposed into smaller subproblems of the same type;

      • subproblems can be solved independently;

      • optimal solutions of the subproblems can be combined to obtain an optimal solution of the original problem;

      • a recurrence relation to compute the optimal value of the problem can be established.

    2. Overlapping Subproblems \(\rightsquigarrow\) the idea is that, when a problem is recursively decomposed into smaller subproblems, the same subproblems may be generated several times.

      In practice, to verify this property one usually checks the following points:

      • the recursive decomposition process generates the same subproblem more than once;

      • it is possible to store the optimal values of the subproblems in a lookup table; then whenever the same subproblem is required again, its optimal value can be retrieved from the lookup table instead of being recomputed.

DP algorithms can be used when a problem has both the Optimal Substructure and Overlapping Subproblems.

16.3 Steps for designing a DP algorithm

  • Identify the recursive decomposition process that, starting from a given problem, generates its subproblems, which are smaller problems of the same type, and verify the following two properties:

    1. the Optimal Substructure property, by checking that an optimal solution of the problem can be obtained by combining the optimal solutions of its subproblems;

    2. the Overlapping Subproblems property, by checking whether the recursive decomposition process generates the same subproblems several times;

  • The construction of a DP algorithm usually follows two main steps:

    1. computation of the optimal value

      • define a recurrence relation that expresses the optimal value of a problem in terms of the optimal values of its subproblems;

      • specify the base cases, i.e., the subproblems whose optimal solution is immediate (the optimal value then follows directly from it);

      • determine a DP algorithm that computes the optimal values of all relevant subproblems, typically in a bottom-up fashion, storing each value in a lookup table so that it is computed only once and retrieved whenever needed again;

    2. construction of an optimal solution

      • specify the information that must be additionally stored in order to reconstruct an optimal solution of the problem.

      • identify the way to construct an optimal solution from the information stored.

16.4 The DP algorithms of this module

  • Every DP algorithm of this module follows the two steps above: a recurrence with its base cases gives the optimal value, an additional table gives an optimal solution.
Problem State Recurrence over Steps
KP \(v(j,k)\) items and capacities \(\Theta(nc)\)
UKP \(v(k)\) capacities \(\Theta(nc)\)
BKP \(v(j,k)\) items and capacities \(\Theta(nc\,b_{\max})\)
SSP \(r(j,k)\) items and target values \(\Theta(nc)\)
MCKP \(v(h,k)\) classes and capacities \(\Theta(nc)\)
MDKP \(v(j,k_1,\dots,k_m)\) items and capacity vectors \(\Theta(m\,n\prod_{d}(c_d+1))\)
KPS \(v(h,k)\), \(u(h,i,k)\) classes, items and capacities \(\Theta(nc)\)
MKP \(v(j,k_1,\dots,k_m)\) items and residual capacities \(\Theta(m\,n\prod_{i}(c_i+1))\)
RCP \(v(\ell)\) rod lengths \(\Theta(n^2)\)
CCP \(v(k)\) amounts of change \(\Theta(nc)\)
ULS \(v(t)\) periods \(\Theta(m^2)\)
CLS \(v(t,k)\) periods and inventories \(O(mDC)\)

  • In all the numerical examples the data are integers: the number of states is finite, and each state is a table cell. The running times \(\Theta(nc)\), \(\Theta(nc\,b_{\max})\) and \(O(mDC)\) contain numbers of the input (a capacity, a bound, a demand), not only its size: they are pseudo-polynomial.

  • With a vector of capacities (MDKP, MKP) the table has one dimension for each capacity: the number of steps is pseudo-polynomial only for a fixed number \(m\) of dimensions or knapsacks.

16.5 Typical mistakes

Warning

  • Using DP without the optimal substructure. If an optimal solution of the problem cannot be built from optimal solutions of the subproblems, the recurrence is wrong.

  • Using DP without overlapping subproblems. If every subproblem appears once, storing the values in a lookup table gives nothing: the DP algorithm is a plain recursion.

  • Forgetting the base cases. The recurrence needs the subproblems whose optimal value is immediate, otherwise the recursion does not stop.

  • Confusing the optimal value with an optimal solution. The table of the optimal values does not give the solution: an additional table of the decisions is needed.

16.6 In summary

In summary

  • A DP algorithm is an exact algorithm that divides a problem into subproblems of the same type, solves them recursively and combines the optimal solutions.

  • It works when the problem has the optimal substructure and overlapping subproblems; the optimal values are stored in a lookup table.

  • The design has two steps: the optimal value (recurrence, base cases, bottom-up table) and an optimal solution (decisions stored and read backwards).

  • Brute force takes exponential time; DP takes a time that is polynomial in the number of states, and pseudo-polynomial when a number of the input is a table dimension.

Exercises on this chapter: Principles