Underlying exponential of KnapsackDynamicProgrammingSolver

[ruqzuq]

The runtime of the exact (KP) solvers based on dynamic programming used in OR tools has already been conclusively investigated from a scientific point of view. [1] Although (KP) is a very simple problem from the perspective of Integer Programming, it is non-trivial due to the combinatorial diversity of the input possibility. Therefore, it makes sense for developers and users to be aware of how solvers work. Mathematical papers often ramble on about new PTAS in search of groundbreaking insights. Therefore, I try to describe the essential features of these solvers from an engineering view.


n = number of items
c = capacity of knapsack


The approach of dynamic programming using the example of (KP) is taught at almost every university. DP-1 is characterized by a (n+1)*(c+1) large table that is iterated in a nested loop. After the computation, backtracking can be used to compose the solution set. DP-1 has no great relevance in practice due to a complexity of O(nc) in time and space. [2]

KnapsackDynamicProgrammingSolver (DP-3) [3] and KnapsackDivideAndConquerSolver (Recursive-DP) [4] build on DP-2, which is implemented in a modified form as SolveSubProblem(). DP-2 works similar to DP-1, but it overwrites a one-dimensional array and does not allow backtracking. [5]

In the following, we consider only the runtimes of DP-1, DP-3 and Recursive-DP for simplicity. The space complexity of DP-1 is O(nc), of DP-3 and Recursive-DP only O(n+c).

Each completed box represents a call to DP-1/DP-2. Each field within a box represents an iteration. The representations are only schematic and simplified to the essentials.




DP-1 calculates the max for all c once for each n and terminates, therefore has a time complexity of O(nc).

Recursive-DP divides n into two partitions of equal size and calls DP-2 twice for each c. This is repeated recursively until the anchor point. So the time complexity is 2nc or O(nc).

The running time of DP-3 depends on which items are in the solution set. In the best case, the indices are small. DP-2 is executed once with n and c, the highest indize from the solution set is returned and is small, so many items are discarded. Subsequent calls have small n and c. In this case, the running time is O(nc) and DP-3 can beat Recursive-DP.

In the Average and Worst Case, the indices of the items from the solution set are high. Thus DP-2 is often called with very high n and c and the time complexity is O(n^2*c).





The comparison in performance between Recursive-DP and DP-3:

Conclusion: KnapsackDynamicProgrammingSolver (DP-3) beats KnapsackDivideAndConquerSolver (Recursive-DP) in certain cases, for example (SSP) with small values. In general for non-trivial (KP) no items can be excluded in advance, so that in most cases and in case of uncertainty one should rather resort to KnapsackDivideAndConquerSolver (Recursive-DP) or Branch and Bound based methods.

[1] Hans Kellerer et al., "Knapsack Problems"
[2] Kellerer, Fig. 2.2. & Fig. 2.3.
[3] Kellerer, Fig. 2.5.
[4] Kellerer, 3.3 Storage Reduction in Dynamic Programming
[5] Kellerer, Fig. 2.4.