Abstract | ||
---|---|---|
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 nondominated 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. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-72845-0_31 | WEA |
Keywords | Field | DocType |
multi-objective knapsack problem,main idea,extensive numerical experiment,present experiment,existing method,exact method,efficient implementation,cpu time,efficient method,dynamic programming,complementary dominance relation,knapsack problem,combinatorial optimization | Dynamic programming,Mathematical optimization,Change-making problem,CPU time,Combinatorial optimization,Theoretical computer science,Continuous knapsack problem,Cutting stock problem,Knapsack problem,Mathematics | Conference |
Volume | ISSN | Citations |
4525 | 0302-9743 | 4 |
PageRank | References | Authors |
0.50 | 8 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cristina Bazgan | 1 | 679 | 62.76 |
Hadrien Hugot | 2 | 47 | 3.25 |
Daniel Vanderpooten | 3 | 1153 | 74.66 |