An efficient implementation for the 0-1 multi-objective knapsack problem
Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2007), An efficient implementation for the 0-1 multi-objective knapsack problem, in Demetrescu, Camil, Experimental Algorithms 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings, Springer : Berlin Heidelberg, p. 406-419
TypeCommunication / Conférence
Book titleExperimental Algorithms 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings
Book authorDemetrescu, Camil
MetadataShow full item record
Abstract (EN)In this paper, we present an approach, based on dynamic programming, for solving 0-1 multi-objective knapsack problems. 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.
Subjects / Keywordsdynamic programming; combinatorial optimization; dominance relations; multi-objective knapsack problem; efficient solutions
Showing items related by title and author.
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é
An efficient procedure for finding best compromise solutions to the multi-objective assignment problem Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2014) Article accepté pour publication ou publié