An Integer Programming-based Local Search for Large-Scale Multidimensional Knapsack Problems

摘要: Integer programming-based local search (IPbLS) is a metaheuristic recently proposed for solving linear combinatorial optimization problems. IPbLS basically the same as first-choice hillclimbing except using integer programming neighbor generation. Meanwhile, multidimensional knapsack problem (MKP) one of most well-known problems and has received wide attention. (IP) very effective small-scale or mid-scale MKP but suffers from large memory requirement large-scale MKP. In this paper, we present an First, initial solution generated by IP, then solutions are repeatedly obtained IP reduction. We used largest 30 instances available on OR-Library experimental data. The method could find better than best-known 6 instances. Furthermore, confirmed that our average result best outperforms method. Keywords-Multidimensional Knapsack Problem; Programming; Programming-based Local Search