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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Exact approaches for the knapsack problem with setups

Thumbnail
Ouvrir
5537.pdf (333.9Kb)
Date
2018
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
Knapsack problems; Column generation; Relaxations; Branch-and-bound algorithms; Computational experiments
Nom de la revue
Computers & Operations Research
Volume
90
Date de publication
02-2018
Pages article
208-220
DOI
http://dx.doi.org/10.1016/j.cor.2017.09.019
URI
https://basepub.dauphine.fr/handle/123456789/18642
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
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é
Résumé en anglais
We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes.

  • 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

 Cette création est mise à disposition sous un contrat Creative Commons.