Gwendal SIMON

Gwendal SIMON


Maître de Conférences, HDR
Département Systèmes Réseaux, Cybersécurité et Droit du numérique

Téléphone : (+33) 2 99 12 70 48
Télécopie : 02 99 12 70 30
Courriel : gwendal.simon@imt-atlantique.fr
ENST Bretagne
Titre

Hard multidimensional multiple choice knapsack problems, an empirical study

Auteur(s)

HAN Bing1, LEBLET Jimmy1, SIMON Gwendal1

Type de document

Article de revue avec comité de lecture

Source

Computers & operations research, january 2009, vol. 37, n° 1, pp. 172-181

Année

2009

Résumé

Recent advances in algorithms for the multidimensional multiple choice knapsack problems have enabled us to solve rather large problem instances. However, these algorithms are evaluated with very limited benchmark instances. In this study, we propose new methods to systematically generate comprehensive benchmark instances. Some instances with special correlation properties between parameters are found to be several orders of magnitude harder than those currently used for benchmarking the algorithms. Experiments on an existing exact algorithm and two generic solvers show that instances whose weights are uncorrelated with the profits are easier compared with weakly or strongly correlated cases. Instances with classes containing similar set of profits for items and with weights strongly correlated to the profits are the hardest among all instance groups investigated. These hard instances deserve further study and understanding their properties may shed light to better algorithms.

Labos

1 : INFO - Dépt. Informatique (Institut Mines-Télécom-Télécom Bretagne-UEB)

Mots clés

Exact algorithm, Performance evaluation, Knapsack problem

Référence

8031

retour à la liste des publications
Technopôle Brest-Iroise - CS 83818 - 29238 Brest Cedex 3 - France
Tél : 33 (0)2 29 00 11 11 - Fax : 33 (0)2 29 00 10 00