A polynomial time algorithm for a cardinality constrained multicriteria knapsack problem

Authors

Abstract

This talk is concerned with the cardinality constrained multicriteria knapsack problem. In this combinatorial optimization problem two binary weight functions and a real valued profit function on the items are given. The task is to choose k out of the n given items with the aim of minimizing the weights and maximizing the profit. Whereas the general multicriteria knapsack problem is known to be NP-hard, we propose an exact algorithm with polynomial running time for our problem. This algorithm computes all nondominated points by
efficiently exploring the weight space.

Conference

24th European Conference on Operational Research (EURO XXIV), July 2010