A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict Graphs - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Expert Systems with Applications Année : 2020

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

(1) , (2) , (2) , (2)
1
2

Résumé

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.

Dates et versions

hal-03617885 , version 1 (23-03-2022)

Identifiants

Citer

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⟩

Collections

U-PICARDIE EPROAD
17 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More