Skip to content

The binary knapsack problem with qualitative levels

Research output: Contribution to journalArticlepeer-review

A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We define a dominance relation over the feasible subsets of the given item set and show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors and we state two greedy algorithms, which efficiently compute a single efficient solution.
Original languageEnglish
Article number0
Pages (from-to)508-514
Number of pages7
JournalEuropean Journal of Operational Research
Issue number2
Early online date25 Jul 2020
Publication statusPublished - 1 Mar 2021


  • The binary knapsack problem

    Accepted author manuscript (Post-print), 297 KB, PDF document

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 25/07/22

    Licence: CC BY-NC-ND

Related information

Relations Get citation (various referencing formats)

ID: 21999526