摘要
把对最大割问题进行秩二松驰的思想应用到二次背包问题上,得到二次背包问题的秩二松驰模型.应用罚函数法求得该模型的最优解,再利用扰动算法将该最优解转化成二次背包问题的解.
The idea of rank two relaxation for max-cut problem is used to quadratic knapsack problem, and the model of the rank two relaxation for quadratic knapsack problem is obtained. The optimal solution to the relaxation is achieved by the penalty function method. Finally the optimal solution of the model is transformed into the solution of quadratic knapsack problem by the rounding algorithm.
出处
《西北师范大学学报（自然科学版）》
CAS
2004年第2期23-24,共2页
Journal of Northwest Normal University(Natural Science)
关键词
二次背包问题
秩二松驰
半定松驰
罚函数法
扰动算法
quadratic knapsack problem
rank two relaxation
semidefinite relaxation
penalty function method
rounding algorithm
