• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the Product Knapsack Problem

Thumbnail
Date
2018
Dewey
Programmation, logiciels, organisation des données
Sujet
Knapsack problem; Dynamic programming; Complexity; Mixed integer (non)linear programming
Journal issue
Optimization Letters
Volume
12
Number
4
Publication date
06-2018
Article pages
691-712
DOI
http://dx.doi.org/10.1007/s11590-017-1227-5
URI
https://basepub.dauphine.fr/handle/123456789/18640
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
D’Ambrosio, Claudia
2071 Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
Furini, Fabio
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monaci, Michele
461036 D.E.I. - University of Bologna.
Traversi, Emiliano
994 Laboratoire d'Informatique de Paris-Nord [LIPN]
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.