期刊名称：International Journal on Computer Science and Engineering
印刷版ISSN：2229-5631
电子版ISSN：0975-3397
出版年度：2011
卷号：3
期号：6
页码：2257-2264
出版社：Engg Journals Publications
摘要：Integer programming-based local search (IPbLS) is a metaheuristic recently proposed for solving linear combinatorial optimization problems. IPbLS is basically the same as the first-choice hillclimbing except for using integer programming for neighbor generation. Meanwhile, the multidimensional knapsack problem (MKP) is one of the most well-known linear combinatorial optimization problems and has received wide attention. Integer programming (IP) is very effective for small-scale or mid-scale MKP but suffers from large memory requirement for large-scale MKP. In this paper, we present an IPbLS for solving large-scale MKP. First, an initial solution is generated by IP, and then neighbor solutions are repeatedly obtained by IP using problem reduction. We used the largest 30 problem instances available on the OR-Library as experimental data. The proposed method could find better solutions than the best-known solutions for 6 problem instances. Furthermore, we confirmed that our average result of the best solutions outperforms the result of the best-known method.
关键词：Multidimensional Knapsack Problem; Integer Programming; Integer Programming-based Local Search
