科研之友
微信
新浪微博
Facebook
分享链接
摘要
We present in this paper a new convex 0-1 QP reformulation for quadratic knapsack problems (QKP). This new reformulation improves the existing reformulation based on diagonal perturbation in the sense that the continuous relaxation of the new reformulation is tighter than or at least as tight as that of the existing reformulation. The improved reformulation is derived from matrix decomposition of the objective function and piecewise linearization of quadratic terms on {0, 1}(n). We show that the optimal parameters in the reformulation can be obtained by solving an SDP problem. Extension to k-item quadratic knapsack problems is also discussed. Computational results are reported to demonstrate the effectiveness of the improved reformulation.
