Large-$W$ limit of the knapsack problem

We formulate the knapsack problem (KP) as a statistical physics system and compute the corresponding partition function as an integral in the complex plane. The introduced formalism allows us to derive three statistical-physics-based algorithms for the KP: one based on the recursive definition of the exact partition function, another based on the large weight limit of that partition function, and a final one based on the zero-temperature limit of the second. Comparing the performances of the algorithms, we find that they do not consistently outperform (in terms of runtime and accuracy) dynamic programming, annealing, or standard greedy algorithms. However, the exact partition function is shown to reproduce the dynamic programming solution to the KP, and the zero-temperature algorithm is shown to produce a greedy solution. Therefore, although dynamic programming and greedy solutions to the KP are conceptually distinct, a statistical physics formalism introduced reveals that the large weight-constraint limit of the former leads to the latter. We conclude by discussing how to extend this formalism in order to obtain more accurate versions of the introduced algorithms and other similar combinatorial optimization problems.

Figure 1

Schematic of accuracy-complexity tradeoff in combinatorial optimization and statistical physics. Combinatorial optimization algorithms are exact, but they often have exponential complexity. $N\gg 1$ statistical physics “algorithms” are approximate but become more accurate as $N$ gets larger, and they have subexponential complexity since they are based on evaluating expressions rather than on enumerating an exponential number of states. The relatively quick $N\gg 1$ limit physical analog of a combinatorial optimization problem should be most accurate in the same numerical regime where the exact optimization algorithm takes the longest time to compute.

Figure 2

Temperature dependence of large-$W$ algorithm: Plots correspond to a KP instance with $N=22$ and a $W=400$. Exact weights and values are provided in the code referenced in the data availability statement along with all the functions used to generate the figures. (a) Plot of Eq. (18) at various temperatures. In the $T\ne 0$ algorithm, we are “rolling down” the hill represented by $F_N\left(z\right)$ [Eq. (18)] and into the local minimum (marked as black circle). As the temperature of the system is lowered, $z_0$ decreases. (b) Calculated value ($\mathbf{v}·\mathbf{X}$) and weight ($\mathbf{w}·\mathbf{X}$) as a function of temperature computed from Eq. (29) with $p_{\text{thresh}}=0.95$. As we lower the temperature, the optimized value increases as does the associated weight, until we reach the weight limit.

Figure 3

Runtime and accuracy comparisons: In (a), (b), and (c), we show the results for the “circle instances,” and in (d), (e), and (f), we show the results for the “spanner instances.” Panels (a) and (d) depict the runtimes as a function of $N$; (b) and (e) depict the accuracy of the algorithms as a function of $N$; (c) and (f) depict the runtime and accuracy for the instance with $N=2048$ items. For the temperature-dependent algorithms, we set $T=1.0$. The large-$W$ algorithms can achieve high accuracies for the strongly correlated circle instance but fail for the highly degenerate spanner instance. The source for the code used to generate these figures is given in the data availability statement.

Figure 4

Relationship between dynamic programming and greedy solutions to the KP: For the statistical physics representation of the KP, taking the $T\to 0$ limit of the exact partition function yields the standard dynamic programming solution, and taking the $T\to 0$ limit of the large-$W$ limit of the partition function yields a greedy solution (Algorithm lg3). The parameter $T$ modulates how far we are from the optimal solution (i.e., lower $T$ corresponds to more optimal solutions). Thus, both Algorithm lg1 and Algorithm lg2 represent, respectively, dynamic and greedy solutions to the KP. In this way, the large-$W$ limit of the dynamic programming solution is a greedy solution.

Figure 5

Runtime and accuracy comparisons: In (a), (b), and (c), we show the results for the “profit-ceiling instances,” and in (d), (e), and (f), we show the results for the “multiple strongly correlated items instances.” Panels (a) and (d) depict the runtimes as a function of $N$; (b) and (e) depict the accuracy of the algorithms as a function of $N$; (c) and (f) depict the runtime and accuracy for the instance with $N=2048$ items. For the temperature-dependent algorithms we set $T=1.0$. The zero-temperature algorithm has increasing performance with increasing $N$ as is consistent with Fig. 1. The source of the code and results used to generate these figures is given in the data availability statement.