| 一类可分离的非线性0-1背包问题的分枝定界算法 |
| |
| 引用本文： | 段玉红,高岳林. 一类可分离的非线性0-1背包问题的分枝定界算法[J]. 甘肃联合大学学报(自然科学版), 2006, 20(6): 1-4,11 |
| |
| 作者姓名： | 段玉红 高岳林 |
| |
| 作者单位： | 1. 宁夏大学,数学与计算机学院,宁夏,银川,750021
2. 宁夏大学,数学与计算机学院,宁夏,银川,750021;西北第二民族学院,信息与计算科学系,宁夏,银川,750021 |
| |
| 基金项目： | 国家民委科研项目基金;宁夏高等学校科研项目 |
| |
| 摘 要： | 构造出了一类可分离非线性0-1背包问题的分枝定界算法．分枝的过程是酱通的0-1变量分枝，用简单的取整启发式法确定更好的可行解；而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近。由此得到最优值的一个下界．数值结果表明所提出的算法是有效的．可以求解中等规模的问题．
|
| 关 键 词： | 0-1背包问题 可分离凹规划 分枝定界方法 线性规划松弛 |
| 文章编号： | 1672-691X（2006）06-0001-05 |
| 收稿时间： | 2006-06-21 |
| 修稿时间： | 2006-06-21 |
Branch and Bound Algorithm for Solving a Class of Nonlinear 0-1 Knapsack Problems |
| |
| DUAN Yu-hong,GAO Yue-lin. Branch and Bound Algorithm for Solving a Class of Nonlinear 0-1 Knapsack Problems[J]. Journal of Gansu Lianhe University :Natural Sciences, 2006, 20(6): 1-4,11 |
| |
| Authors: | DUAN Yu-hong GAO Yue-lin |
| |
| Abstract: | A branch and bound algorlthm for solving a class of nonllnear 0-1 knapsack problems is proposed ,In whlch branching is common 0-1 varlables one and a better feaslble solutiong is found by a simply Integer hevrlstle method as well as a lower bound of the optlmal velue of the subproblem in the each branching node is determined by solving linear programming relaxed appronimate problem to be obtalned with linear relaned technique,It is shown by thd numerleal result that the algorlthm is effective and can solve the mlddle scale problems. |
| |
| Keywords: | 0-1 knapsack problem separable concave programming branch and bound,linear programming relan |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
