报告题目：关于背包问题凸化方法的研究
Improved 0-1 Convex QP Reformulations for Quadratic Knapsack Problems
报告人：冀淑慧，复旦大学博士
时 间：2012年06月20日 周三下午 2:30—3:30
地 点：闵行数学楼126室

摘 要：We present in this talk 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 also discuss the extensions of the reformulation to k-item QKP and chance-constrained QKP.