论文标题
一般多维背包问题的统计力学分析
Statistical mechanics analysis of general multi-dimensional knapsack problems
论文作者
论文摘要
背包问题（KP）是一个代表性的组合优化问题，旨在通过在总权重的给定约束下选择项目子集来最大化总利润。在这项研究中，我们分析了KP的广义版本，该版本称为广义多维背包问题（GMDKP）。与基本KP相反，GMDKP允许在多个重量约束下每个项目类型多种选择。尽管已经知道了几种有效的算法，并且对基本KP的溶液的性质进行了很大的检查，但对于GMDKP的溶液特性的研究很少。为了深入了解该问题，我们使用副本方法评估了GMDKP随机合奏的典型可实现的总利润限制。我们的发现总结如下：（1）当商品类型的利润正态分布时，总利润在主要顺序上相对于项目类型的数量增长，因为每项类型的最大选择数量$ x^{\ rm max} $增加，而仅取决于$ x^{\ rm max} $，如果在$ x^{\ rm rm max} $中，则在sub-max} $中不变。 （2）贪婪型启发式方法可以找到一个几乎最佳的解决方案，其总利润仅通过低计算成本的子领先顺序低于最佳值。 （3）基于空腔方法的启发式算法可以改善最佳总利润的子领先差异。广泛的数值实验支持这些发现。
Knapsack problem (KP) is a representative combinatorial optimization problem that aims to maximize the total profit by selecting a subset of items under given constraints on the total weights. In this study, we analyze a generalized version of KP, which is termed the generalized multidimensional knapsack problem (GMDKP). As opposed to the basic KP, GMDKP allows multiple choices per item type under multiple weight constraints. Although several efficient algorithms are known and the properties of their solutions have been examined to a significant extent for basic KPs, there is a paucity of known algorithms and studies on the solution properties of GMDKP. To gain insight into the problem, we assess the typical achievable limit of the total profit for a random ensemble of GMDKP using the replica method. Our findings are summarized as follows: (1) When the profits of item types are normally distributed, the total profit grows in the leading order with respect to the number of item types as the maximum number of choices per item type $x^{\rm max}$ increases while it depends on $x^{\rm max}$ only in a sub-leading order if the profits are constant among the item types. (2) A greedy-type heuristic can find a nearly optimal solution whose total profit is lower than the optimal value only by a sub-leading order with a low computational cost. (3) The sub-leading difference from the optimal total profit can be improved by a heuristic algorithm based on the cavity method. Extensive numerical experiments support these findings.
