ABSTRACT

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.