Journal
OPTIMIZATION LETTERS
Volume 12, Issue 4, Pages 691-712Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-017-1227-5
Keywords
Knapsack problem; Dynamic programming; Complexity; Mixed integer (non)linear programming
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available