Improved results on the 0-1 multidimensional knapsack problem
Improved results on the 0-1 multidimensional knapsack problem
复制标题
DOI：
10.1016/j.ejor.2004.01.024
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
Michel Vasquez;Yannick Vimont
中科院分区：
文献类型：
--
作者：
Michel Vasquez;Yannick Vimont
几何约束和切割平面已成功地用于解决0-1多维背包问题。我们的算法结合了线性规划与一个有效的禁忌搜索。它给出了最好的结果时，与其他算法的基准发布的OR库。将该算法嵌入到变量固定启发式算法中，仍然改进了我们以前的结果。此外，可以从500个原始变量中产生大约100个变量的困难子问题。这些小问题总是很难解决。
Geometric Constraint and Cutting planes have been successfully used to solve the 0–1 multidimensional knapsack problem. Our algorithm combines Linear Programming with an efficient tabu search. It gives best results when compared with other algorithms on benchmarks issued from the OR-Library. Embedding this algorithm in a variables fixing heuristic still improves our previous results. Furthermore difficult sub problems with about 100 variables issued from the 500 original ones could be generated. These small sub problems are always very hard to solve.