This paper is devoted to a knapsack problem with a cardinality constraint when dropping the assumption of additive representability [10]. More precisely, we assume that we only have a classification of the items into ...
详细信息
ISBN:
(纸本)9783642248726
This paper is devoted to a knapsack problem with a cardinality constraint when dropping the assumption of additive representability [10]. More precisely, we assume that we only have a classification of the items into ordered classes. We aim at generating the set of preferred subsets of items, according to a pairwise dominance relation between subsets that naturally extends the ordering relation over classes [4,16]. We first show that the problem reduces to a multiobjective knapsack problem with cardinality constraint. We then propose two polynomial algorithms to solve it, one based on a multiobjective dynamic programming scheme and the other on a multiobjective branch and bound procedure. We conclude by providing numerical tests to compare both approaches.
暂无评论