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

Abstract

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.

Keywords:

• 0-1 quadratic knapsack problem
• Lagrangian dual
• SDP relaxation
• uniqueness of optimal solution

Acknowledgement

This work was supported by National Natural Science Foundation of China under grants 11101092, 10971034 and 70832002, by the Joint NSFC/RGC grants under grant 71061160506 and by Research Grants Council of Hong Kong under grant 414207.