A note on semidefinite relaxation for 0-1 quadratic knapsack problems

摘要

We investigate in this note solution properties of semidefinite programming (SDP) relaxation for 0-1 quadratic knapsack problem (QKP). In particular, we focus on the issue of uniqueness of the optimal solution to the SDP relaxation for QKP. We first give a counterexample which shows that the optimal solution to the SDP relaxation for QKP could be non-unique. This is in contrast with the case of unconstrained 0-1 quadratic problems. A necessary and sufficient condition is then derived to ensure the uniqueness of the optimal solution to the SDP relaxation for QKP.