A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Annals of Operations Research Année : 2021

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

(1) , (2)
1
2

Résumé

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.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

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

Collections

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

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More