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

被引:19
作者
Dahmani, Isma [1 ]
Hifi, Mhand [2 ]
Saadi, Toufik [2 ]
Yousef, Labib [2 ]
机构
[1] USTHB, AMCD RO, BP 32 El Alia, Algiers 16111, Algeria
[2] UPJV, EPROAD EA 4669, 7 Rue Moulin Neuf, F-80000 Amiens, France
关键词
Knapsack; Optimization; Population; Particle swarm; LOCAL SEARCH;
D O I
10.1016/j.eswa.2020.113224
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页数:13
相关论文
共 31 条
[1]   Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls [J].
Akbar, MM ;
Rahman, MS ;
Kaykobad, M ;
Manning, EG ;
Shoja, GC .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (05) :1259-1273
[2]   Discrete particle swarm optimization method for the large-scale discrete time-cost trade-off problem [J].
Aminbakhsh, Saman ;
Sonmez, Rifat .
EXPERT SYSTEMS WITH APPLICATIONS, 2016, 51 :177-185
[3]  
[Anonymous], P INT C EV COMP WORL
[4]  
[Anonymous], SUSTAINABILITY
[5]  
[Anonymous], SEM EPROAD EA U PIC
[6]   An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem [J].
Billionnet, A ;
Soutif, T .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 157 (03) :565-575
[7]   An iterated "hyperplane exploration" approach for the quadratic knapsack problem [J].
Chen, Yuning ;
Hao, Jin-Kao .
COMPUTERS & OPERATIONS RESEARCH, 2017, 77 :226-239
[8]   Three pseudo-utility ratio-inspired particle swarm optimization with local search for multidimensional knapsack problem [J].
Chih, Mingchang .
SWARM AND EVOLUTIONARY COMPUTATION, 2018, 39 :279-296
[9]   Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem [J].
Chih, Mingchang .
APPLIED SOFT COMPUTING, 2015, 26 :378-389
[10]  
Clerc M., 1999, Proc. of The Congress on Evolutionary Computation, V3, P1951