Abstract

This note corrects some spreadsheet formulas and typographical errors in Raffensperger & Richard, "Implementing Dynamic Programs in Spreadsheets."

Errors in "Implementing Dynamic Programs in Spreadsheets"

Our paper, "Implementing Dynamic Programs in Spreadsheets," has a number of spreadsheet formula mistakes and typographical errors. This short note describes the errors and gives improved versions. We indicate changes in bold red font.

Errors in Section 3.

In Figure 3d, one of the Key Cell Formulas should read:
D6, "=VLOOKUP(D$5-$A6,$A$6:$B$20,2)+$S6", copied to
E6:Q7, F8:Q8, G9:Q9,... Q19:Q19.

The last sentence in the second paragraph below Figure 3d should read:
This value of $16 is noted in row 22 in cell I22, then transposed to column S in cell S12, to be used in later calculations."

The first sentence of the fourth paragraph below Figure 3d should read:
"In Figure 3d, we must copy formulas carefully for each level of capacity. If the formulas are copied to the entire rectangle D6:Q19, we have a circular reference."

The section "Designing a DP in a spreadsheet: the classic recursion for the knapsack," beginning with the paragraph just above Figure 4 describes the primal retrieval for the knapsack DP, but the primal retrieval formula was incorrect. The error may be seen in Figures 4 through 7, which show the "Optimal items" as four of size 3 and one of size 4. However, the capacity used is 4*3+4=16, which is larger than the knapsack capacity of 14. so many references must be corrected. Rather than give all references, figures, and spreadsheets piecemeal, the following text replaces the section beginning with the paragraph just above Figure 4.

So how do we find the optimal solution (Figure 4)? Row 22 shows the maximum profit possible at each stage, based on the incoming arcs in cells C6:Q20. But these maxima may not be optimal. Row 23 determines the optimal capacity used at each stage. The formula in cell D23 subtracts the optimal item size from the capacity used to obtain the capacity used in the next stage. Row 24 shows the optimal item sizes that we should pack: we can optimally pack two items of size 7, for a total profit of $44. The formula in row 24 works by first checking whether the optimal capacity used equals the capacity of the current stage, then looks up the item size in column A.

Enlarge
Click here to download

Our next implementation can be found in Winston (2003). The primal retrieval is original. This implementation avoids the need for transposition. In fact, the fundamental algorithm is quite different from the previous versions, being the following O(nb) recursion of Gilmore & Gomory (1966).

For the knapsack problem, max cx, ax≤b, where a is the vector of sizes, x is the vector of decision variables and b is the scalar capacity, the Gilmore & Gomory recursion is:

    for i = 0,…, b, f(i) = max_{j=1,…,n, i ≥ aj} {c_j + f(i − a_j)}.

The algorithm itself contains no transposition, so neither does the graphical spreadsheet implementation in Figure 5.

Click here to download

So how does this spreadsheet work? It lists arcs in the dynamic program, but fewer than in Figures 3 and 4. Those earlier examples have an arc from each possible capacity to every greater possible capacity. In fact, we need only the arcs associated with each possible capacity and each item. For example, consider the selected cell, D15, in Figure 5. The row label for cell D15 is 5, meaning that we have 5 units of capacity available. The column label for cell D15 is x3, item 3, with size 4 and value $12. Observe that we have recursively already packed the capacity of 4 optimally, with a value of $12, as found in cell F14. The formula in D15 first checks to make sure that item 3 will fit in size 5. It will, so the formula looks up an item of size 1, discovers it has value $0, which means we can still add this item of size 4, and get a value of $12. This value of 12 would be noted in the Max Profit column F, but we actually did better with item 1 of size 5 and value $16.

As before, "Max profit" shows the best way to pack each value of capacity - if that were the only capacity available. As in the previous example, "Capacity used" shows the optimal capacity used at each stage. The "Optimal items" shows the size of the optimal items to pack. The primal retrieval is almost the same as the previous example, but the MATCH() function returns the alternate optimum of two items of value $16 and one item of value $12.

Let us analyze the constructive complexity. This implementation requires four distinct formulas. After entering the data in rows 5, 6, and 7, the values 0, …,14 in column A are entered, then the formulas in columns B through E are entered, all O(1) operations. Next, the MAX() formulas are entered into column F, another O(1) operation. Finally, the primal retrieval is added in columns G and H. The spreadsheet has 5 distinct formulas. An instance with b=1,000 and n=200 would also have only 5 distinct formulas. Therefore, this spreadsheet is of O(1) constructive complexity. Within the knapsack capacity, changing the size or profit of items is trivial. To increase the capacity, we simply select the last three rows (excluding the optimal objective) and fill downwards (overwriting the objective). We then add the objective again in column H, pointing to the last cell in column G. To add another item requires inserting a column, perhaps between E and F, and then checking the MAX() formula. Thus, this model can be revised in O(1) time.

The thoughtful reader may observe that the data entry in the previous model, Figure 4, appears to be O(b), while the data entry in this model, Figure 5, is O(n). However, we have assumed that the rectangular fill in Figure 4, A6:B20, could be done in O(1) time. Then, if B6:B20 in Figure 4 were initialized with zeroes, the data entry would be only O(n), which is sunk.

Our next example knapsack, Figure 6, was suggested by an anonymous referee, and is a significant improvement from an earlier draft. The primal retrieval is original. The spreadsheet has just one distinct formula for the recursion, and this formula is reasonably short. Primal retrieval requires three more formulas. The spreadsheet needs only 4b total formulas. As such, it may prove useful to the practitioner. The user enters item profits in column B, for each possible size in column A. Changing the profits or sizes of items up to the capacity is trivial. Compared with the previous example, the dimension of items has been collapsed into an array formula.

The formula in column D uses an array function to find a previous size row equals the previous profit row. Without checking both size and profit, a formula could sometimes get the wrong local optimum. The formula in D returns the local optimal profit. Now focus on cell E21. This formula chooses a particular optimal solution among possible multiple optima. It can then work backwards (up the spreadsheet) to find a complete primal solution. Based on Column E, column F then calculates the optimal size for the chosen optimal profit path.

Click here to download

Modifying this spreadsheet is straightforward, but we need to keep in mind how a dynamic program works. To add capacity, insert rows between rows 20 and 21. Starting with rows 17, 18, and 19, use the fill handle to fill data and formulas downwards. Thus, the spreadsheet can be written or revised in O(1) time. This implementation uses fewer cells than earlier versions, O(b) cells, rather than O(b²) or O(nb) cells. We were able to solve a knapsack with capacity 1,000, with random profits, in just a minute or so.

The last knapsack DP implementation lists the arcs as a database. The database lookup function, DMAX() serves in place of the MAX() function used above. In his book on Lotus 1-2-3, LP, and DP, Ho (1987) observes a connection between DPs and databases. "In dynamic programming, you do not actually write down a problem in the process of formulating it. Instead, you identify aspects of the problem which will serve as the key components in a DP model. In this sense, a DP model looks more like a database than a clear-cut optimization problem."

This spreadsheet works very much as the previous ones, with a different layout and different lookup functions. It enumerates all possible arcs in the dynamic program as a one-dimension list. Consider the selected cell, C17, in Figure 7. The formula finds the value $12 for an item of size 4 − 0, then adds this value to the best current objective $0 for a capacity of 0. This value of $12 is recorded in the Max Profit row 8, cell F8, for use in later calculation.

Enlarge
Click here to download

This spreadsheet first requires an O(1) operation to create the table in rows 5 to 8. The spreadsheet has eight distinct formulas, all of which are O(1) operations, as shown in Figure 7. This spreadsheet therefore has constructive complexity of O(1). For each possible size in row 6, the user enters the object profits in row 7. Like the first knapsack implementation, changing the size or profit of items below the capacity is trivial. The user needs only to change the Profit data in row 7. Adding t more units of capacity requires inserting t columns in the summary table at the top, and then copying nt +t²/2−t/2 rows downwards, both of which are O(1) operations. The range in each database formula in row 8 needs to be corrected, but this could be avoided if rows were inserted at the bottom of the database, and anyway this is also an O(1) operation.

If the node label formulas in A14:B118 are converted to values, then the database can be sorted various ways. The modeler may want to think about dominated arcs, could graph the data in various ways, and could export the arcs to a linear programming solver such as AMPL or Lingo, perhaps with another column for the arc cost. Such a formulation could be used to solve the one-dimensional cutting stock problem using the formulation of Dyckhoff (1981) or Carvalho (1998).

Errors in Section 4.

The recursion equation just before Figure 8a should read:
f(0)=0, f(k)=min_{1 ≤ i ≤ k}(max(f(k−i), r_k)+p_k−i+1) for 1 ≤ k ≤ n.

Figure 8a may be better understood with the following image.

Enlarge
Figure 8a. DP network for scheduling a batching machine.

Error in Section 5.

The first recursion formula contains an unnecessary reference to the subscript j. The formula should read
f₀(t) = 0, for t ≥ 0.

Error in References.

The following reference had an incorrect author name:
Dreyfus, S.E. and M.A. Law, (1977), The Art and Theory of Dynamic Programming, Academic Press, New York, NY.

Acknowledgement

Our thanks to Art Lew for observing the errors and suggesting improvements to the paper.

References

de Carvalho, J.M. Valério (1998), "Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound," International Transactions in Operations Research, Vol. 5, No. 1, pp. 35-44.

Dreyfus, S.E. and A.M. Law, (1977), The Art and Theory of Dynamic Programming, Academic Press, New York, NY.

Dyckhoff, H. (1981), "A New Linear Programming Approach to the Cutting Stock Problem," Operations Research, Vol. 29, No. 6, Nov-Dec.

Gilmore, P.C. and R.E. Gomory (1966), "The Theory and Computation of Knapsack Functions," Operations Research, Vol. 14, No. 1, pp. 1045-1074.

Ho, J.K., (1987), Linear and dynamic programming with Lotus 1-2-3, Release 2, Management Information Source, Portland, OR.

Raffensperger, J. F. and R. Pascal. (2005), "Implementing Dynamic Programs in Spreadsheets," INFORMS Transactions on Education, Vol. 5, No 2,

Winston, W., (2003), Operations Research: Applications and Algorithms, 4^th edition, Duxbury Press, Belmont, CA.

To reference this paper, please use:  Raffensperger, J. F. and R. Pascal. (2005), "Implementing Dynamic Programs in Spreadsheets," INFORMS Transactions on Education, Vol. 5, No 2,  http://ite.pubs.informs.org/Vol5No2/RaffenspergerRichard/