| 二次背包问题的秩二松驰 |
| |
| 引用本文： | 黄静静 凌永祥 徐凤敏. 二次背包问题的秩二松驰[J]. 西北师范大学学报(自然科学版), 2004, 40(2): 23-24 |
| |
| 作者姓名： | 黄静静 凌永祥 徐凤敏 |
| |
| 作者单位： | 西安交通大学理学院，西安交通大学理学院，西安交通大学理学院 陕西西安 710049，陕西西安 710049，陕西西安 710049 |
| |
| 摘 要： | 把对最大割问题进行秩二松驰的思想应用到二次背包问题上,得到二次背包问题的秩二松驰模型.应用罚函数法求得该模型的最优解,再利用扰动算法将该最优解转化成二次背包问题的解.
|
| 关 键 词： | 二次背包问题 秩二松驰 半定松驰 罚函数法 扰动算法 |
| 文章编号： | 1001-988X(2004)02-0023-02 |
| 修稿时间： | 2003-04-21 |
Rank two relaxation to the quadratic knapsack problem |
| |
| HUANG Jing-jing,LING Yong-xiang,XU Feng-min. Rank two relaxation to the quadratic knapsack problem[J]. Journal of Northwest Normal University Natural Science (Bimonthly), 2004, 40(2): 23-24 |
| |
| Authors: | HUANG Jing-jing LING Yong-xiang XU Feng-min |
| |
| Abstract: | 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. |
| |
| Keywords: | quadratic knapsack problem rank two relaxation semidefinite relaxation penalty function method rounding algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
