An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
复制标题
DOI：
10.1016/s0377-2217(03)00244-3
复制
发表时间：
2004-09
期刊：
影响因子：
--
通讯作者：
A. Billionnet;Éric Soutif
中科院分区：
文献类型：
--
作者：
A. Billionnet;Éric Soutif
0-1二次背包问题(QKP)是指在线性容量约束下，使一个系数为正的二次伪布尔函数最大化的问题。在本文中，我们提出了一种解决这一问题的确切方法。该方法利用拉格朗日分解得到(QKP)的一个上界的计算。它允许我们找到最多150个变量的实例，无论它们的密度如何，并且对于中低密度，最多300个变量。
The 0–1 quadratic knapsack problem (QKP) consists in maximizing a quadratic pseudo-Boolean function with positive coefficients subject to a linear capacity constraint. In this paper we present an exact method to solve this problem. This method makes use of the computation of an upper bound for (QKP) which is derived from Lagrangian decomposition. It allows us to find the optimum of instances with up to 150 variables whatever their density, and with up to 300 variables for medium and low density.