Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs

Abstract : The knapsack problem arises in a variety of real world applications, including flexible manufacturing systems, railway stations, hydrological studies and others. In this paper, we propose a descent method-based heuristic for tackling a special knapsack problem: the binary quadratic knapsack with conflict graphs. The proposed method combines (i) an intensification search with a descent method for enhancing the accuracy of the solutions and (ii) a diversification strategy which is used for enlarging the search space. The method uses degrading and re-optimization strategies in order to reach a series of diversified solutions. The performance of the proposed method is evaluated on benchmark instances taken from the literature, where its achieved results are compared to those reached by both GLPK solver and the best method available in the literature. The method seems very competitive, where it is able to achieve 37 new lower bounds.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617884
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:05
Dernière modification le : mercredi 31 août 2022 - 18:26:30

Identifiants

Collections

Citation

Isma Dahmani, Mhand Hifi. A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs. Annals of Operations Research, Springer Verlag, 2021, 298 (1-2, SI), pp.125-147. ⟨10.1007/s10479-019-03290-3⟩. ⟨hal-03617884⟩

Partager

Métriques

Consultations de la notice

4