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

A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict Graphs

Abstract : The knapsack problem arises in a variety of real world applications such as railway stations, flexible manufacturing systems, multimedia, cryptography and hydrological studies. In this paper, a special case of the knapsack problem is tackled: the quadratic knapsack problem with conflict graphs. This problem is solved by using a population-based search algorithm, which is inspired from the binary particle swarm optimization combined with a quick and efficient local search. The particle swarm optimization generates a population of particles while the local search procedure tries either to repair the infeasibility of each binary solution or to improve its quality. The performance of the proposed method is evaluated on a set of benchmark instances taken from the literature (containing medium and large-scale instances), where its achieved results are compared to those published in the literature containing the bounds realized with GLPK, Cplex and those achieved by more recent methods. The proposed method remains competitive, where encouraging results have been obtained. (C) 2020 Published by Elsevier Ltd.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617885
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:05
Dernière modification le : jeudi 24 mars 2022 - 03:00:21

Lien texte intégral

Identifiants

Collections

Citation

Isma Dahmani, Mhand Hifi, Toufik Saadi, Labib Yousef. A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict Graphs. Expert Systems With Applications, 2020, 148, ⟨10.1016/j.eswa.2020.113224⟩. ⟨hal-03617885⟩

Partager

Métriques

Consultations de la notice

9