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

George Mavrotas, Kostas Florios () and José Rui Figueira

Applied Mathematics and Computation, 2015, vol. 270, issue C, 25-43

Abstract: 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.

Keywords: Combinatorial optimization; Branch-and-bound; Evolutionary computations; Metaheuristics; Multi-objective programming; Multi-dimensional knapsack problems (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300315010735
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:270:y:2015:i:c:p:25-43

DOI: 10.1016/j.amc.2015.08.018

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().