The binary knapsack problem with qualitative levels

Luca E. Schäfer; Tobias Dietz; Maria Barbati; José Rui Figueira; Salvatore Greco; Stefan Ruzika

doi:10.1016/j.ejor.2020.07.040

The binary knapsack problem with qualitative levels

Luca E. Schäfer, Tobias Dietz, Maria Barbati, José Rui Figueira, Salvatore Greco, Stefan Ruzika

Research output: Contribution to journal › Article › peer-review

122 Downloads (Pure)

Abstract

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 language	English
Article number	0
Pages (from-to)	508-514
Number of pages	7
Journal	European Journal of Operational Research
Volume	289
Issue number	2
Early online date	25 Jul 2020
DOIs	https://doi.org/10.1016/j.ejor.2020.07.040
Publication status	Published - 1 Mar 2021

Keywords

Computing science
Knapsack problem
Non-dominance
Qualitative levels
Dynamic programming

Access to Document

10.1016/j.ejor.2020.07.040

The binary knapsack problemAccepted author manuscript (Post-print), 297 KBLicence: CC BY-NC-ND

Cite this

@article{2296eb90d20a47768b8b73ff18cae633,

title = "The binary knapsack problem with qualitative levels",

abstract = "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.",

keywords = "Computing science, Knapsack problem, Non-dominance, Qualitative levels, Dynamic programming",

author = "Sch{\"a}fer, {Luca E.} and Tobias Dietz and Maria Barbati and Figueira, {Jos{\'e} Rui} and Salvatore Greco and Stefan Ruzika",

year = "2021",

month = mar,

day = "1",

doi = "10.1016/j.ejor.2020.07.040",

language = "English",

volume = "289",

pages = "508--514",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - The binary knapsack problem with qualitative levels

AU - Schäfer, Luca E.

AU - Dietz, Tobias

AU - Barbati, Maria

AU - Figueira, José Rui

AU - Greco, Salvatore

AU - Ruzika, Stefan

PY - 2021/3/1

Y1 - 2021/3/1

N2 - 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.

AB - 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.

KW - Computing science

KW - Knapsack problem

KW - Non-dominance

KW - Qualitative levels

KW - Dynamic programming

UR - https://linkinghub.elsevier.com/retrieve/pii/S0377221720306664

U2 - 10.1016/j.ejor.2020.07.040

DO - 10.1016/j.ejor.2020.07.040

M3 - Article

SN - 0377-2217

VL - 289

SP - 508

EP - 514

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

M1 - 0

ER -

The binary knapsack problem with qualitative levels

Abstract

Keywords

Access to Document

Fingerprint

Cite this