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.
| Original language | English |
|---|---|
| Pages (from-to) | 930-942 |
| Journal | Optimization Methods and Software |
| Volume | 28 |
| Issue number | 4 |
| Online published | 8 Dec 2011 |
| DOIs | |
| Publication status | Published - 1 Aug 2013 |
| Externally published | Yes |
Research Keywords
- 0-1 quadratic knapsack problem
- Lagrangian dual
- SDP relaxation
- uniqueness of optimal solution
Fingerprint
Dive into the research topics of 'A note on semidefinite relaxation for 0-1 quadratic knapsack problems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver