• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2018
Journal name
Optimization Letters
Volume
12
Number
4
Pages
691-712
Publication identifier
10.1007/s11590-017-1227-5
Metadata
Show full item record
Author(s)
D’Ambrosio, Claudia cc
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
D.E.I. - University of Bologna.
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 programming

Related items

Showing items related by title and author.

  • Thumbnail
    Exact approaches for the knapsack problem with setups 
    Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
  • Thumbnail
    Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation 
    Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
  • Thumbnail
    A hybrid heuristic for the multi-activity tour scheduling problem 
    Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié
  • Thumbnail
    Theoretical and computational study of several linearisation techniques for binary quadratic problems 
    Furini, Fabio; Traversi, Emiliano (2018) Article accepté pour publication ou publié
  • Thumbnail
    Shortest Path Problem variants for the Hydro Unit Commitment Problem 
    Ackooij, Wim van; D'Ambrosio, Claudia; Liberti, Leo; Taktak, Raouia; Thomopulos, Dimitri; Toubaline, Sónia (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo