摘要
对二次背包问题提出两种半定规划松弛SDP1和SDP2 ,从理论上证明了SDP2 能给出更好的上界 。
We investigate two SDP relaxations of the quadatic knapsack problem and prove that SDP 2 gives a better upper bound in theory and in numerical experiment.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2001年第5期638-640,658,共4页
Journal of Xidian University
基金
陕西省自然科学基金资助项目 ( 99SL0 2 )
关键词
二次背包问题
半定规划
松驰
quadratic knapsack problem
semidefinite programming
relaxation
