Statistical mechanics of the multi-constraint continuous knapsack problem

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.

Statistical mechanical analysis of linear programming relaxation for combinatorial optimization problems

Typical behavior of the linear programming (LP) problem is studied as a relaxation of the minimum vertex cover (min-VC), a type of integer programming (IP) problem. A lattice-gas model on the Erdös-Rényi random graphs of α-uniform hyperedges is proposed to express both the LP and IP problems of the min-VC in the common statistical mechanical model with a one-parameter family. Statistical mechanical analyses reveal for α=2 that the LP optimal solution is typically equal to that given by the IP below the critical average degree c=e in the thermodynamic limit. The critical threshold for good accuracy of the relaxation extends the mathematical result c=1 and coincides with the replica symmetry-breaking threshold of the IP. The LP relaxation for the minimum hitting sets with α≥3, minimum vertex covers on α-uniform random graphs, is also studied. Analytic and numerical results strongly suggest that the LP relaxation fails to estimate optimal values above the critical average degree c=e/(α-1) where the replica symmetry is broken.

Effect of quantum fluctuation in error-correcting codes

We discuss the decoding performance of error-correcting codes based on a model in which quantum fluctuations are introduced by means of a transverse field. The essential issue in this paper is whether quantum fluctuations improve the decoding quality compared with the conventional estimation based on thermal fluctuations, which is called finite-temperature decoding. We found that an estimation incorporating quantum fluctuations approaches the optimal performance of finite-temperature decoding. The results are illustrated by numerically solving saddle-point equations and performing a Monte Carlo simulation. We also evaluated the upper bound of the overlap between the original sequence and the decoded sequence derived from the equations of state for the order parameters, which is a measure of the decoding performance.