Skip to content

DP for the rod cutting problem

Part 3 · Dynamic programming · Chapter 28 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Rod cutting (RCP)

Prerequisites

Objectives

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

  • state the RCP, encode a solution as a vector of numbers of pieces, and explain why cutting patterns and vectors are different objects;

  • write the recurrence \(v(\ell)\) and explain it, base case included;

  • run the DP algorithm by hand with the top-down and the bottom-up approach, and with the running best value \(m\);

  • reconstruct an optimal solution from the vector \({s}\), for the rod and for every shorter rod;

  • write the second recurrence \(v(j,\ell)\) on pairs (largest piece length, rod length) and count the steps of the DP algorithm.

The problem of this chapter is the rod cutting problem (RCP): its definition is on its page.

28.1 Instances and feasible solutions

Example 28.1: Rod cutting problem

We consider a rod of length \(n = 4\) and a set \(\{1,2,3,4\}\) of \(4\) possible piece lengths with the following profits:

\[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

We refer to this RCP instance as Example 28.1.

The number of possible solutions of the RCP is \(2^{n-1}\) since we can cut a rod of length \(n\) in \(2^{n-1}\) different ways, with an independent option of cutting (or not) at each possible cutting position.

  • The number of possible RCP solutions grows exponentially with the length \(n\) of the rod:

    \[ 2^{n-1} = O(2^n). \]

    Therefore, enumerating all possible solutions quickly becomes impractical as \(n\) increases.

28.1.1 Encoding of feasible solutions

A feasible solution of the RCP is a way of cutting the rod into pieces, such that the total length of the pieces is equal to the rod length.

  • An RCP feasible solution can be described by an integer solution vector

    \[ (x_1,x_2,\dots,x_n) \]

    where each component has the following meaning:

    \[ x_\ell = \text{number of pieces of length } \ell, \qquad \forall \ell \in \{1,2,\dots,n\}; \]

    The number of pieces is

    \[ \sum_{\ell=1}^{n} x_\ell. \]

    Since the solution is feasible, the total length of the pieces must be equal to the rod length:

    \[ \sum_{\ell=1}^{n} \ell \, x_\ell = n. \]

    The total profit of a feasible solution is

    \[ \sum_{\ell=1}^{n} p_\ell x_\ell. \]

  • Two or more cutting patterns may have the same vector representation: the vector records how many pieces of each length are obtained, but it does not specify the order in which the pieces are cut.

  • Cutting patterns with the same vector representation have the same total profit, since the order in which the pieces are cut does not affect the obtained pieces and therefore does not affect the total profit.

Example 28.2: Enumeration of all possible RCP solutions

We consider the RCP instance of Example 28.1 with a rod of length \(n = 4\) and the profits associated with the possible piece lengths are:

\[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

There are \(2^{4-1} = 8\) feasible solutions, corresponding to the different ways of cutting the rod.

In the following binary tree, each level corresponds to a possible cutting position: an edge labeled \(1\) means that the rod is cut at that length, while an edge labeled \(0\) means that it is not cut at that length. Each leaf represents one complete cutting pattern and reports the corresponding vector.

Figure 1

The figure below shows all possible cutting patterns associated with the leaves of the previous tree, through the labels \((1),(2),\dots,(8)\). For each obtained piece, the number written inside the piece is its length, while the number above it is its profit.

Figure 2

Label Solution vector Number of pieces Total profit
\((1)\) \((0,0,0,1)\) \(1\) \(9\)
\((2)\) \((1,0,1,0)\) \(2\) \(8+1=9\)
\((3)\) \((0,2,0,0)\) \(2\) \(5+5=10\)
\((4)\) \((2,1,0,0)\) \(3\) \(5+1+1=7\)
\((5)\) \((1,0,1,0)\) \(2\) \(1+8=9\)
\((6)\) \((2,1,0,0)\) \(3\) \(1+5+1=7\)
\((7)\) \((2,1,0,0)\) \(3\) \(1+1+5=7\)
\((8)\) \((4,0,0,0)\) \(4\) \(1+1+1+1=4\)

  • Overview

    Instances and feasible solutions · Encoding of feasible solutions

    Open

  • 28.2 A first DP algorithm

    Open

  • 28.3 A second DP algorithm

    Open

  • Typical mistakes · In summary

    In summary

    Open

Next: 28.2 A first DP algorithm

Exercises on this chapter: Rod cutting (RCP)