A Hybrid Algorithm for the Unbounded Knapsack Problem

Abstract : This paper presents a new approach for exactly solving the Unbounded Knapsack Problem (UKP) and proposes a new bound that was proved to dominate the previous bounds on a special class of UKP instances. Integrating bounds within the framework of sparse dynamic programming led to the creation of an efficient and robust hybrid algorithm, called EDUK2. This algorithm takes advantage of the majority of the known properties of UKP, particularly the diverse dominance relations and the important periodicity property. Extensive computational results show that, in all but a very few cases, EDUK2 significantly outperforms both MTU2 and EDUK, the currently available UKP solvers, as well the well-known general purpose mathematical programming optimizer CPLEX of ILOG. These experimental results demonstrate that the class of hard UKP instances needs to be redefined, and the authors offer their insights into the creation of such instances.
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00335065
Contributeur : Rumen Andonov <>
Soumis le : mardi 28 octobre 2008 - 12:54:53
Dernière modification le : mercredi 11 avril 2018 - 01:59:49
Document(s) archivé(s) le : lundi 7 juin 2010 - 19:40:42

Fichier

jvers08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Vincent Poirriez, Nicola Yanev, Rumen Andonov. A Hybrid Algorithm for the Unbounded Knapsack Problem. Discrete Optimization, Elsevier, 2009, 6, pp.110-124. 〈10.1016/j.disopt.2008.09.004〉. 〈inria-00335065〉

Partager

Métriques

Consultations de la notice

482

Téléchargements de fichiers

638