Solving efficiently the 0-1 multi-objective knapsack problem
Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009), Solving efficiently the 0-1 multi-objective knapsack problem, Computers and Operations Research, 36, 1, p. 260-279. http://dx.doi.org/10.1016/j.cor.2007.09.009
TypeArticle accepté pour publication ou publié
Nom de la revueComputers and Operations Research
MétadonnéesAfficher la notice complète
Résumé (EN)In this paper, we present an approach, based on dynamic programming, for solving the 0–1 multi-objective knapsack problem. The main idea of the approach relies on the use of several complementary dominance relations to discard partial solutions that cannot lead to new non-dominated criterion vectors. This way, we obtain an efficient method that outperforms the existing methods both in terms of CPU time and size of solved instances.Extensive numerical experiments on various types of instances are reported. A comparison with other exact methods is also performed. In addition, for the first time to our knowledge, we present experiments in the three-objective case.
Mots-clésDynamic programming; Dominance relations; Efficient solutions; Non-dominated criterion vectors; Combinatorial optimization; Multi-objective knapsack problem
Affichage des éléments liés par titre et auteur.
Discrete representation of the non-dominated set for multi-objective optimization problems using kernels Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié