Thumbnail

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

View/Open
Type
Communication / Conférence
Date
2007
Conference country
ITALY
Book title
Experimental Algorithms 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings
Book author
Demetrescu, Camil
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-540-72844-3
Pages
406-419
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Hugot, Hadrien
Vanderpooten, Daniel
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 / Keywords
dynamic programming; combinatorial optimization; dominance relations; multi-objective knapsack problem; efficient solutions