25.2.2 A DP algorithm for the ULS: Step 1 and Step 2

Part 3 · Dynamic programming · Chapter 25 · Chapter 25: Uncapacitated lot sizing (ULS) · Lecture notes, volume 3 (PDF) · Slides · Exercises: Uncapacitated lot sizing (ULS) · App: Wagner-Whitin for uncapacitated lot sizing

• Step 1: computation of the optimal value

  For any \(t \in \{1,2,\dots,m\}\), let \(v(t)\) be the optimal value of the ULS subinstance given by:

  1. a set \(\{1,2,\dots,t\}\) of \(t\) time periods,

  2. for each period \(j \in \{1,2,\dots,t\}\), a demand \(d_j\),

  3. for each period \(j \in \{1,2,\dots,t\}\), a setup cost \(sc_j\), a variable production cost \(vc_j\), and a holding cost \(hc_j\).

  The recursive formula to compute \(v(t)\) reads as follows:

  \[\begin{equation*} \label{eq:ww} v(t)= \left\{ \begin{array}{ll} \displaystyle \min \bigg\{ v(j-1) + c_{j,t} : j \in \{1,2,\dots,t\}\bigg\} & \textrm{if $1\le t \le m$,}\\[2ex] 0 & \textrm{if $t=0$.} \end{array} \right. \tag{25.3} \end{equation*}\]

  • The subinstance with periods \(\{1,\dots,t\}\) is a ULS instance of the same type: its inventory must be empty at the end of period \(t\). Here, \(v(0)=0\), since an empty set of periods has no demand and no cost.

  • The recursive decomposition process of formula \(\eqref{eq:ww}\) generates \(t\) independent subproblems, each corresponding to a possible choice of the period \(j\) of the last production run, which produces the demands of periods \(j,\dots,t\).

  • By the zero-inventory ordering property applied to the subinstance, the inventory is empty at the end of period \(j-1\), and the residual subproblem is the ULS subinstance with periods \(\{1,\dots,j-1\}\).

  • The optimal value \(v(t)\) is obtained by trying all possible periods of the last production run and selecting the one that minimizes the sum \(v(j-1)+c_{j,t}\) of the optimal value of the residual subproblem and the cost of the last run.

  • Hence, an optimal solution for periods \(\{1,\dots,t\}\) is built by combining the chosen last production run in period \(j\) with an optimal solution of the residual subproblem with periods \(\{1,\dots,j-1\}\).

    \(\rightsquigarrow\) Optimal Substructure verified!

  • Different choices of the last production run, possibly made for different values of \(t\), can lead to the same residual set of periods, and therefore the same value \(v(t)\) may need to be computed several times during the recursive evaluation of formula \(\eqref{eq:ww}\).

    \(\rightsquigarrow\) Overlapping Subproblems verified!

  • A first method to compute the optimal value \(v(m)\) of the ULS instance is the top-down approach. The method starts from the call with \(t=m\) and evaluates formula \(\eqref{eq:ww}\) recursively: each call for periods \(\{1,\dots,t\}\) triggers further calls for periods \(\{1,\dots,j-1\}\), for all \(j \in \{1,2,\dots,t\}\), until the base case \(v(0)\) is reached.

  • The recursion tree of the function \(v\) has one node for each recursive call, labeled with the function call it represents. The root represents the initial call. The children of a node represent the recursive calls made by that call. The leaf nodes represent the base cases.

    Example 25.5: Recursion tree

    We consider the first four periods of the ULS instance of Example 25.1 (with five periods the tree has \(32\) nodes). This is the recursion tree of the top-down approach to compute \(v(4)\):

    

    The children of a node \(v(t)\) are ordered by \(j\in\{1,\dots,t\}\): the child \(v(j-1)\) corresponds to a last production run in period \(j\). The function \(v\) is called \(16\) times, and the same subproblems are solved multiple times: \(v(2)\) is called \(2\) times, \(v(1)\) is called \(4\) times, and \(v(0)\) is called \(8\) times. All the other calls are made only once.

  • The value \(v(t)\), for a generic period \(t\), can be computed once the values \(v(j)\) are known for all smaller periods \(j<t\).

    Example 25.6: Computing the values of the \(v\) function

    We consider the ULS instance of Example 25.1, with the matrix \({c}\) of the production-run costs:

    \[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

    The value of the function \(v\) can be computed by starting from the base case \(v(0)=0\) and then computing the values of \(v(1)\), \(v(2)\), \(v(3)\), \(v(4)\), and \(v(5)\) in order, as follows:

    • Since we know the value of \(v(0)\), we can compute \(v(1)\), as follows:

      \[ v(1)=v(0)+c_{1,1}=0+50=50 \]

    • Once we have computed \(v(1)\) and \(v(0)\), we can compute \(v(2)\), as follows:

      \[\begin{align*} v(2)&=\min\{v(0)+c_{1,2},v(1)+c_{2,2}\}\\ &=\min\{0+60,50+50\}=60 \end{align*}\]

    • Once we have computed \(v(2)\), \(v(1)\) and \(v(0)\), we can compute \(v(3)\), as follows:

      \[\begin{align*} v(3)&=\min\{v(0)+c_{1,3},v(1)+c_{2,3},v(2)+c_{3,3}\}\\ &=\min\{0+120,50+80,60+50\}=110 \end{align*}\]

    • Once we have computed \(v(3)\), \(v(2)\), \(v(1)\) and \(v(0)\), we can compute \(v(4)\), as follows:

      \[\begin{align*} v(4)&=\min\{v(0)+c_{1,4},v(1)+c_{2,4},v(2)+c_{3,4},v(3)+c_{4,4}\}\\ &=\min\{0+240,50+160,60+90,110+50\}=150 \end{align*}\]

    • Once we have computed \(v(4)\), \(v(3)\), \(v(2)\), \(v(1)\) and \(v(0)\), we can compute \(v(5)\), as follows:

      \[\begin{align*} v(5)&=\min\{v(0)+c_{1,5},v(1)+c_{2,5},v(2)+c_{3,5},v(3)+c_{4,5},v(4)+c_{5,5}\}\\ &=\min\{0+280,50+190,60+110,110+60,150+50\}=170 \end{align*}\]

  • We can avoid solving the same subproblems repeatedly by storing the value of each subproblem as soon as it is computed. The values are stored in a lookup table, the vector \({v}[0..m]\), whose cell \({v}[t]\) contains \(v(t)\).

  • Since solving a subproblem with value \(v(t)\) depends only on subproblems with values \(v(j-1)\), with \(j-1<t\), we can solve the subproblems for increasing values of \(t\), starting from the base case \(v(0)=0\) and building up to \(v(m)\): this observation naturally leads to a much more efficient method to compute the optimal value \(v(m)\) of the ULS instance.

  • A second method to compute the optimal value \(v(m)\) of the ULS instance is the bottom-up approach. The method starts from the base case \(v(0)=0\) and evaluates formula \(\eqref{eq:ww}\) for increasing periods \(t \in \{1,2,\dots,m\}\): each value \(v(t)\) is computed using the already-computed values \(v(0), v(1), \dots, v(t-1)\), until the value \(v(m)\) of the ULS instance is obtained.

    This is the pseudo-code of the DP algorithm using the bottom-up approach:

    Algorithm: DP_WW

    Input: A ULS instance given by the number \(m\) of periods and the arrays \(d[1..m]\), \(sc[1..m]\), \(vc[1..m]\), \(hc[1..m]\)

    Output: The optimal value

    1Function DP_WW(\(m,d,sc,vc,hc\))

    2\({c} := \textnormal{CostMatrix}(m,d,sc,vc,hc)\)

    3\({v} := \textnormal{new array}[0..m]\)

    4\({v}[0] \leftarrow 0\)

    5for \(t := 1\) to \(m\) do

    6\(\mathit{b} := +\infty\)

    7for \(j := 1\) to \(t\) do

    8if \({v}[j-1] + {c}[j][t] < \mathit{b}\) then

    9\(\mathit{b} \leftarrow {v}[j-1] + {c}[j][t]\)

    10end

    11end

    12\({v}[t] \leftarrow \mathit{b}\)

    13end

    14return \({v}[m]\)

    • The matrix \({c}\) contains the production-run costs, computed by the algorithm CostMatrix.

    • The vector \({v}[0..m]\) is the lookup table: it stores the optimal values of all subproblems, with the base case \({v}[0]=0\).

    • The outer loop, over \(t \in \{1,2,\dots,m\}\), computes \({v}[t]\) in increasing order of the last period.

    • The inner loop, over \(j \in \{1,2,\dots,t\}\), evaluates all possible periods of the last production run and keeps in \(\mathit{b}\) the smallest value \({v}[j-1]+{c}[j][t]\); the variable \(\mathit{b}\) starts from \(+\infty\), so the first comparison always updates it.

    • At the end of the inner loop, \({v}[t] \leftarrow \mathit{b}\) stores the optimal value \({v}[t]\).

    • Finally, the optimal value \({v}[m]\) of the ULS instance is returned.

    Example 25.7: Execution of the DP algorithm

    We consider the ULS instance of Example 25.1, with the matrix \({c}\) of the production-run costs:

    \[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

    For each step of the DP algorithm, the table shows the values of \(t\) and \(j\), the current value of \(\mathit{b}\), and the cell \({v}[t]\). The cell of \(\mathit{b}\) is highlighted in red when updated; the cell of \({v}[t]\) is highlighted in blue when assigned.

    \(t\)	\(j\)	\({v}[t]\)	\(\mathit{b}\)	Action
    \(-\)	\(-\)	0	\(-\)	\({v}[0]\leftarrow 0\)
    	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
    1	1	\(-\)	50	\({v}[0]{+}{c}[1][1]=0{+}50=50<+\infty\): \(\mathit{b}\leftarrow 50\)
    	\(-\)	50	50	\({v}[1]\leftarrow \mathit{b}=50\)
    	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
    2	1	\(-\)	60	\({v}[0]{+}{c}[1][2]=0{+}60=60<+\infty\): \(\mathit{b}\leftarrow 60\)
    	2	\(-\)	60	\({v}[1]{+}{c}[2][2]=50{+}50=100>60\): no update
    	\(-\)	60	60	\({v}[2]\leftarrow \mathit{b}=60\)
    	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
    3	1	\(-\)	120	\({v}[0]{+}{c}[1][3]=0{+}120=120<+\infty\): \(\mathit{b}\leftarrow 120\)
    	2	\(-\)	120	\({v}[1]{+}{c}[2][3]=50{+}80=130>120\): no update
    	3	\(-\)	110	\({v}[2]{+}{c}[3][3]=60{+}50=110<120\): \(\mathit{b}\leftarrow 110\)
    	\(-\)	110	110	\({v}[3]\leftarrow \mathit{b}=110\)
    	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
    4	1	\(-\)	240	\({v}[0]{+}{c}[1][4]=0{+}240=240<+\infty\): \(\mathit{b}\leftarrow 240\)
    	2	\(-\)	210	\({v}[1]{+}{c}[2][4]=50{+}160=210<240\): \(\mathit{b}\leftarrow 210\)
    	3	\(-\)	150	\({v}[2]{+}{c}[3][4]=60{+}90=150<210\): \(\mathit{b}\leftarrow 150\)
    	4	\(-\)	150	\({v}[3]{+}{c}[4][4]=110{+}50=160>150\): no update
    	\(-\)	150	150	\({v}[4]\leftarrow \mathit{b}=150\)
    	\(-\)	\(-\)	\(+\infty\)	\(\mathit{b}\leftarrow +\infty\)
    5	1	\(-\)	280	\({v}[0]{+}{c}[1][5]=0{+}280=280<+\infty\): \(\mathit{b}\leftarrow 280\)
    	2	\(-\)	240	\({v}[1]{+}{c}[2][5]=50{+}190=240<280\): \(\mathit{b}\leftarrow 240\)
    	3	\(-\)	170	\({v}[2]{+}{c}[3][5]=60{+}110=170<240\): \(\mathit{b}\leftarrow 170\)
    	4	\(-\)	170	\({v}[3]{+}{c}[4][5]=110{+}60=170=\mathit{b}\): no update
    	5	\(-\)	170	\({v}[4]{+}{c}[5][5]=150{+}50=200>170\): no update
    	\(-\)	170	170	\({v}[5]\leftarrow \mathit{b}=170\)

    This is the vector \({v}\) after the execution of the DP algorithm:

    \[ \begin{array}{c|cccccc} \hline & {t=0} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {{v}[t]} & 0 & 50 & 60 & 110 & 150 & 170 \\ \hline \end{array} \]

  • After the execution of the DP algorithm, the vector \({v}\) contains the optimal value \({v}[t]\) for every set of periods \(\{1,\dots,t\}\).

  • Remark (shortest path). Formula \(\eqref{eq:ww}\) computes a shortest path in a network with nodes \(0,1,\dots,m\) and one arc from node \(j-1\) to node \(t\), of cost \(c_{j,t}\), for every \(j\le t\). The value \(v(t)\) is the length of a shortest path from node \(0\) to node \(t\). This is the shortest-path formulation of Chapter 15 «Formulations of lot sizing problems», without the capacities: an arc is a production run.

• Step 2: computation of an optimal solution

  • To compute an optimal solution, it is necessary to store some additional information.

  • For each period \(t\), in addition to the optimal value \({v}[t]\), we store \({r}[t]\), the period of the last production run in an optimal solution for periods \(\{1,\dots,t\}\).

  • Starting from \(t=m\), the value \({r}[t]\) gives the period of the last production run, which produces \(D_{{r}[t],t}\) units; the remaining periods are \(\{1,\dots,{r}[t]-1\}\), and the same rule can be applied again, and so on, until no period remains.

    This is the pseudo-code of the DP algorithm using the bottom-up approach with the storing of the information necessary to compute an optimal solution:

    Algorithm: DP_WW_InfoSol

    Input: A ULS instance given by the number \(m\) of periods and the arrays \(d[1..m]\), \(sc[1..m]\), \(vc[1..m]\), \(hc[1..m]\)

    Output: The optimal value and the information vector \({r}[1..m]\)

    1Function DP_WW_InfoSol(\(m,d,sc,vc,hc\))

    2\({c} := \textnormal{CostMatrix}(m,d,sc,vc,hc)\)

    3\({v} := \textnormal{new array}[0..m]\)

    4\({r} := \textnormal{new array}[1..m]\)

    5\({v}[0] \leftarrow 0\)

    6for \(t := 1\) to \(m\) do

    7\(\mathit{b} := +\infty\)

    8\(\mathit{a} := 0\)

    9for \(j := 1\) to \(t\) do

    10if \({v}[j-1] + {c}[j][t] < \mathit{b}\) then

    11\(\mathit{b} \leftarrow {v}[j-1] + {c}[j][t]\)

    12\(\mathit{a} \leftarrow j\)

    13end

    14end

    15\({v}[t] \leftarrow \mathit{b}\)

    16\({r}[t] \leftarrow \mathit{a}\)

    17end

    18return \({v}[m], {r}\)

    • The DP algorithm uses the additional temporary variable \(\mathit{a}\) to keep track of the decision made when \(\mathit{b}\) is updated. If the last production run in period \(j\) is selected, \(\mathit{a}\leftarrow j\) stores this decision. At the end of the inner loop, \({r}[t]\leftarrow \mathit{a}\) stores the period of the selected last production run, together with the optimal value \({v}[t]\leftarrow \mathit{b}\).

    • Because of the strict comparison, in case of ties the smallest period \(j\) is stored.

    Example 25.8: Computation of the additional information

    We consider the ULS instance of Example 25.1, with the matrix \({c}\) of the production-run costs:

    \[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

    For each step of the DP algorithm, the table shows the values of \(t\) and \(j\), the cell \({r}[t]\), the current value of \(\mathit{b}\), and the current value of \(\mathit{a}\). The cell of \(\mathit{b}\) is highlighted in red when updated; the cell of \(\mathit{a}\) and the cell of \({r}[t]\) are highlighted in blue when updated.

    \(t\)	\(j\)	\({r}[t]\)	\(\mathit{b}\)	\(\mathit{a}\)	Action
    \(-\)	\(-\)	\(-\)	\(-\)	\(-\)	Initial state
    	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
    1	1	\(-\)	50	1	\({v}[0]{+}{c}[1][1]=0{+}50=50<+\infty\): \(\mathit{b}\leftarrow 50\), \(\mathit{a}\leftarrow 1\)
    	\(-\)	1	50	1	\({v}[1]\leftarrow \mathit{b}=50\), \({r}[1]\leftarrow \mathit{a}=1\)
    	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
    2	1	\(-\)	60	1	\({v}[0]{+}{c}[1][2]=0{+}60=60<+\infty\): \(\mathit{b}\leftarrow 60\), \(\mathit{a}\leftarrow 1\)
    	2	\(-\)	60	1	\({v}[1]{+}{c}[2][2]=50{+}50=100>60\): no update
    	\(-\)	1	60	1	\({v}[2]\leftarrow \mathit{b}=60\), \({r}[2]\leftarrow \mathit{a}=1\)
    	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
    3	1	\(-\)	120	1	\({v}[0]{+}{c}[1][3]=0{+}120=120<+\infty\): \(\mathit{b}\leftarrow 120\), \(\mathit{a}\leftarrow 1\)
    	2	\(-\)	120	1	\({v}[1]{+}{c}[2][3]=50{+}80=130>120\): no update
    	3	\(-\)	110	3	\({v}[2]{+}{c}[3][3]=60{+}50=110<120\): \(\mathit{b}\leftarrow 110\), \(\mathit{a}\leftarrow 3\)
    	\(-\)	3	110	3	\({v}[3]\leftarrow \mathit{b}=110\), \({r}[3]\leftarrow \mathit{a}=3\)
    	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
    4	1	\(-\)	240	1	\({v}[0]{+}{c}[1][4]=0{+}240=240<+\infty\): \(\mathit{b}\leftarrow 240\), \(\mathit{a}\leftarrow 1\)
    	2	\(-\)	210	2	\({v}[1]{+}{c}[2][4]=50{+}160=210<240\): \(\mathit{b}\leftarrow 210\), \(\mathit{a}\leftarrow 2\)
    	3	\(-\)	150	3	\({v}[2]{+}{c}[3][4]=60{+}90=150<210\): \(\mathit{b}\leftarrow 150\), \(\mathit{a}\leftarrow 3\)
    	4	\(-\)	150	3	\({v}[3]{+}{c}[4][4]=110{+}50=160>150\): no update
    	\(-\)	3	150	3	\({v}[4]\leftarrow \mathit{b}=150\), \({r}[4]\leftarrow \mathit{a}=3\)
    	\(-\)	\(-\)	\(+\infty\)	0	\(\mathit{b}\leftarrow +\infty\), \(\mathit{a}\leftarrow 0\)
    5	1	\(-\)	280	1	\({v}[0]{+}{c}[1][5]=0{+}280=280<+\infty\): \(\mathit{b}\leftarrow 280\), \(\mathit{a}\leftarrow 1\)
    	2	\(-\)	240	2	\({v}[1]{+}{c}[2][5]=50{+}190=240<280\): \(\mathit{b}\leftarrow 240\), \(\mathit{a}\leftarrow 2\)
    	3	\(-\)	170	3	\({v}[2]{+}{c}[3][5]=60{+}110=170<240\): \(\mathit{b}\leftarrow 170\), \(\mathit{a}\leftarrow 3\)
    	4	\(-\)	170	3	\({v}[3]{+}{c}[4][5]=110{+}60=170=\mathit{b}\): no update
    	5	\(-\)	170	3	\({v}[4]{+}{c}[5][5]=150{+}50=200>170\): no update
    	\(-\)	3	170	3	\({v}[5]\leftarrow \mathit{b}=170\), \({r}[5]\leftarrow \mathit{a}=3\)

    This is the vector \({r}\) after the execution of the DP algorithm:

    \[ \begin{array}{c|ccccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 & 3 \\ \hline \end{array} \]

  • Once the vector \({r}\) has been computed, an optimal solution of the ULS instance can be computed by repeatedly applying the following rule, starting from \(t=m\) and \(x_j=0\) for all \(j \in \{1,2,\dots,m\}\):

    \[ x_{{r}[t]} \leftarrow D_{{r}[t],t}, \qquad t \leftarrow {r}[t]-1, \]

    until \(t=0\). This yields the vector \((x_1,x_2,\dots,x_m)\), where each entry \(x_j\) is the number of units produced in period \(j\) in an optimal solution.

  • The following pseudo-code implements the computation of an optimal solution, given the vector \({r}\).

    Algorithm: DP_WW_SolComputation

    Input: The number \(m\) of periods and the demands \(d[1..m]\) of the ULS instance, and the vector \({r}[1..m]\)

    Output: An optimal solution of the ULS instance

    1Function DP_WW_SolComputation(\(m,d,{r}\))

    2\(x := \textnormal{new array}[1..m]\)

    3for \(j := 1\) to \(m\) do

    4\(x[j] \leftarrow 0\)

    5end

    6\(t := m\)

    7while \(t > 0\) do

    8\(x[{r}[t]] \leftarrow \sum_{k={r}[t]}^{t} d[k]\)

    9\(t \leftarrow {r}[t] - 1\)

    10end

    11return \(x\)

    Example 25.9: Computing an optimal solution

    After the execution of the DP algorithm on the instance of Example 25.1, we have the following vector \({r}\):

    \[ \begin{array}{c|ccccc} \hline & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {{r}[t]} & 1 & 1 & 3 & 3 & 3 \\ \hline \end{array} \]

    We can compute an optimal solution for \(m=5\) periods as follows:

    Iteration	\(t\)	\({r}[t]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	\(x[5]\)	\(t\leftarrow {r}[t]-1\)
    \(-\)	\(-\)	\(-\)	0	0	0	0	0	\(t=5\)
    \(1\)	\(5\)	\(3\)	0	0	80	0	0	\(t=3-1=2\)
    \(2\)	\(2\)	\(1\)	30	0	80	0	0	\(t=1-1=0\)

    • \(t=5\), \({r}[5]=3\): the last production run of periods \(1,\dots,5\) is in period \(3\) and covers the demands of periods \(3,\dots,5\), so \(x[3]\leftarrow d_{3}+d_{4}+d_{5}=30+40+10=80\)

    • \(t=2\), \({r}[2]=1\): the last production run of periods \(1,\dots,2\) is in period \(1\) and covers the demands of periods \(1,\dots,2\), so \(x[1]\leftarrow d_{1}+d_{2}=20+10=30\)

    An optimal solution is the vector:

    \[ (30,\allowbreak 0,\allowbreak 80,\allowbreak 0,\allowbreak 0) \]

    The corresponding optimal value is \({v}[5]=170\), the same value obtained by the enumeration of Example 25.3 and by Gurobi on the \(\mathrm{ILP}_{\mathrm{ULS}}\) model.

  • Remark (ties). In the computation of \({v}[5]\), the run in period \(4\) gives the same value as the run in period \(3\), but the strict comparison keeps \(j=3\). Choosing \(j=4\) instead leads to the other optimal solution \((30,\allowbreak 0,\allowbreak 30,\allowbreak 50,\allowbreak 0)\) of Example 25.3. The DP algorithm returns one optimal solution, not all of them.

25.2.3 Number of steps

• Let \(S_c(m)\) denote the number of steps executed by CostMatrix in the worst case, where \(m\) is the number of periods. The number of executions of its lines is:

  • Line 2 is executed \(1\) time.

  • Line 3, Line 4, Line 5, and Line 6 are executed \(m\) times each.

  • Line 7, Line 8, Line 9, and Line 10 are executed \(\displaystyle\sum_{j=1}^{m}(m-j)=\frac{m(m-1)}{2}\) times each.

  • Line 13 is executed \(1\) time.

  Therefore,

  \[ S_c(m)=2+4m+4\cdot\frac{m(m-1)}{2}=2m^2+2m+2. \]

• Let \(S(m)\) denote the number of steps executed by DP_WW in the worst case. Line 2 executes CostMatrix, that is, \(S_c(m)\) steps. In the worst case, the condition at line 8 is true at every iteration of the inner loop, and therefore line 9 is executed as often as line 8. The number of executions of the other lines is:

  • Line 3 is executed \(1\) time.

  • Line 4 is executed \(1\) time.

  • Line 5 is executed \(m\) times.

  • Line 6 is executed \(m\) times.

  • Line 7 is executed \(\displaystyle\sum_{t=1}^{m}t\) times.

  • Line 8 is executed \(\displaystyle\sum_{t=1}^{m}t\) times.

  • Line 9 is executed \(\displaystyle\sum_{t=1}^{m}t\) times.

  • Line 12 is executed \(m\) times.

  • Line 14 is executed \(1\) time.

  Therefore, the total number of steps in the worst case is

  \[ S(m)=S_c(m)+3+3m+3\sum_{t=1}^{m}t =2m^2+2m+2+3+3m+3\cdot\frac{m(m+1)}{2} =\frac{7m^2+13m+10}{2}. \]

  Hence,

  \[ S(m)=\Theta(m^2). \]

  Indeed,

  \[ \lim_{m\to\infty} \frac{\frac{7m^2+13m+10}{2}}{m^2} = \lim_{m\to\infty} \frac{1}{2}\left(7+\frac{13}{m}+\frac{10}{m^2}\right) = \frac{7}{2}\in\mathbb{R}_{>0}. \]

  The DP algorithm executes

  \[ S(m)=\Theta(m^2) \]

  steps in the worst case.

• DP_WW_InfoSol only adds a constant number of operations inside the same loops, and therefore its number of steps has the same order of growth.

---

Next: Typical mistakes · In summary