On the Product Knapsack Problem
D’Ambrosio, Claudia; Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018), On the Product Knapsack Problem, Optimization Letters, 12, 4, p. 691-712. 10.1007/s11590-017-1227-5
Type
Article accepté pour publication ou publiéDate
2018Journal name
Optimization LettersVolume
12Number
4Pages
691-712
Publication identifier
Metadata
Show full item recordAuthor(s)
D’Ambrosio, Claudia
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monaci, Michele
Traversi, Emiliano
Laboratoire d'Informatique de Paris-Nord [LIPN]
Abstract (EN)
Given a set of items, each characterized by a profit and a weight, we study the problem of maximizing the product of the profits of the selected items, while respecting a given capacity. To the best of our knowledge this is the first manuscript that studies this variant of the knapsack problem which we call Product Knapsack Problem (PKP). We show that PKP is weakly NP-hard. We propose and implement a Dynamic Programming algorithm and different Mixed Integer Linear and Nonlinear Programming formulations for the PKP. Finally, we present an extensive computational study on a large set of benchmark instances derived from the literature.Subjects / Keywords
Knapsack problem; Dynamic programming; Complexity; Mixed integer (non)linear programmingRelated items
Showing items related by title and author.
-
Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
-
Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
-
Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié
-
Furini, Fabio; Traversi, Emiliano (2018) Article accepté pour publication ou publié
-
Ackooij, Wim van; D'Ambrosio, Claudia; Liberti, Leo; Taktak, Raouia; Thomopulos, Dimitri; Toubaline, Sónia (2018) Article accepté pour publication ou publié