An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics

摘要

In this paper we propose an improved version of a core based algorithm for the multi-objective extension of one of the most well-known combinatorial optimization problems, the multi-dimensional knapsack problem. The original algorithm was designed only for bi-objective problems combining an extension of the core concept and a branch-and-bound algorithm. It is a deterministic algorithm and the core concept exploits the “divide and conquer” solution strategy which proves very effective in such problems. The new version is not limited to bi-objective problems; it can effectively handle problems with more than two objective functions and it has features that greatly accelerate the solution process. Namely, these features are the use of a heuristic based on the Dantzig bound in the fathoming process and the better housekeeping of the incumbent list through filtering of solutions. The key parameters of the new algorithm are (a) the size of the core and (b) the number of provided cores. Varying these parameters the user can easily tune the size of the obtained Pareto set. A comparison with evolutionary algorithms, like NSGA–II, SPEA2 and MOEA/D, has been made according to run time and the most widely used metrics (set coverage, set convergence etc). Our new version performs better than the most popular evolutionary algorithms and it is comparable to very recent state-of-the-art metaheuristics, like Multi-objective Memetic Algorithm based on Decomposition (MOMAD), for multi-objective programming.