| 多维背包问题的变邻域填充函数算法 |
| |
| 引用本文： | 林耿,朱文兴.多维背包问题的变邻域填充函数算法[J].福州大学学报(自然科学版),2012,40(1):14-21. |
| |
| 作者姓名： | 林耿 朱文兴 |
| |
| 作者单位： | 闽江学院数学系;福州大学离散数学与理论计算机科学研究中心 |
| |
| 基金项目： | 国家自然科学基金资助项目(61070020,61170308);福建省教育厅科研资助项目(JA11201);闽江学院科研育苗资助项目(YKY1012) |
| |
| 摘 要： | 首先给出解的两个邻域结构,并把多维背包问题转化为相应的无约束整数规划问题.其次构造一个单参数的填充函数,然后提出一类求解多维背包问题的变邻域填充函数算法.实验结果表明,该算法是有效的.
|
| 关 键 词： | 多维背包问题 填充函数 变邻域 |
A filled function based variable neighborhood search method for the multidimensional knapsack problem |
| |
| LIN Geng,ZHU Wen-xing.A filled function based variable neighborhood search method for the multidimensional knapsack problem[J].Journal of Fuzhou University(Natural Science Edition),2012,40(1):14-21. |
| |
| Authors: | LIN Geng ZHU Wen-xing |
| |
| Institution: | 1.Department of Mathematics,Minjiang University,Fuzhou,Fujian 350108,China; 2.Center for Discrete Mathematics and Theoretical Computer Science,Fuzhou University,Fuzhou,Fujian 350108,China) |
| |
| Abstract: | The multidimensional knapsack problem is one of classical NP-hard problems.Firstly,this paper presents two neighborhoods of a solution,and converts multidimensional knapsack problem equivalently into unconstrained integer programming.Next,a filled function with only one adjustable parameter is constructed.Then a filled function based variable neighborhood search method for multidimensional knapsack problem is proposed.Numerical results show that the proposed algorithm is efficient. |
| |
| Keywords: | multidimensional knapsack problem filled function variable neighborhood search |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 |
