Solving efficiently the 0–1 multi-objective knapsack problem

详细信息	查看全文 | 推荐本文 |

• 作者：Cristina Bazgan ; Hadrien Hugot ; Daniel V ; erpooten
• 关键词：Multi-objective knapsack problem ; Non-dominated criterion vectors ; Efficient solutions ; Dynamic programming ; Dominance relations ; Combinatorial optimization
• 刊名：Computers and Operations Research
• 出版年：2009
• 期刊代码：3_03050548
• 类别：dec
• 出版时间：January 2009
• 卷：36
• 期：1
• 页码：260-279
• 文件大小：379 K

摘要

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.