0-1 Quadratic Knapsack Problems: An Exact Approach Based on a t-Linearization
0-1 Quadratic Knapsack Problems: An Exact Approach Based on a t-Linearization
复制标题
0-1 二次背包问题：基于 t 线性化的精确方法
DOI：
10.1137/110820762
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Serigne Gueye
中科院分区：
文献类型：
--
作者：
C. Rodrigues;Dominique Quadri;P. Michelon;Serigne Gueye
本文提出了一种基于线性化方法的0-1二次背包问题的精确求解方法，该方法包括在线性容量约束下最大化一个非负系数的二次伪布尔函数.与传统的线性化方案相比，我们的方法只增加了一个额外的变量。建议的线性化框架提供了一个严格的上限，这是在一个分支和定界计划。这个上界与[A. Billionnet，A. Faye和E. Soutif，European J. Oper.结果：第112（1999）号来文，英文本第100页。664- 672]，以及我们的分支定界格式[W. D. Pisinger，A. B。Rasmussen和R. Sandvik，INFORMS J. COMPUT.，19（2007），pp. 280- 290]。实验结果表明，我们的上限是相当有竞争力的（小于1美元的最优值）。此外，建议的分支和界限显然优于Pisinger等人开发的算法。低密度的情况下（25\%$）的所有实例…
This paper presents an exact solution method based on a new linearization scheme for the 0-1 quadratic knapsack problem, which consists of maximizing a quadratic pseudo-Boolean function with nonnegative coefficients subject to a linear capacity constraint. Contrasting with traditional linearization schemes, our approach adds only one extra variable. The suggested linearization framework provides a tight upper bound, which is used in a branch-and-bound scheme. This upper bound is numerically compared with that of [A. Billionnet, A. Faye, and E. Soutif, European J. Oper. Res., 112 (1999), pp. 664--672], and our branch-and-bound scheme with the exact algorithm of [W. D. Pisinger, A. B. Rasmussen, and R. Sandvik, INFORMS J. Comput., 19 (2007), pp. 280--290]. The experiments show that our upper bound is quite competitive (less than $1\%$ from the optimum). In addition, the proposed branch-and-bound clearly outperforms the algorithm developed by Pisinger et al. for low density instances ($25\%$) for all instanc...