A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem. (July 2017)

• Record Type: Journal Article
• Authors: Avci, Mustafa; Topaloglu, Seyda
• Is Part Of: Computers & operations research. Volume 83(2017)
• Page Start: 54
• Page End: 65
• Publication Date: 2017-07
• Subjects: Generalized quadratic multiple knapsack problem -- Variable neighborhood descent -- Iterated local search -- Perturbation mechanism; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.02.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The generalized quadratic multiple knapsack problem is studied. A multi-start iterated local search algorithm is developed for its solution. The algorithm combines an adaptive perturbation mechanism with local search. 35 out of 48 best known solutions are improved for large-size problem instances. Abstract: The quadratic multiple knapsack problem (QMKP) is a variant of the classical knapsack problem where multiple knapsacks are considered and the objective is to maximize a quadratic objective function subject to capacity constraints. The generalized quadratic multiple knapsack problem (G-QMKP) extends the QMKP by considering the setups, assignment conditions and the knapsack preferences of the items. In this study, a multi-start iterated local search algorithm (MS-ILS) in w the variable neighborhood descent (VND) algorithm is integrated with an adaptive perturbation mechanism is proposed to solve the G-QMKP. The multi-start implementation together with the adaptive perturbation mechanism enables the search process to explore different search regions in the search space while VND is applied to obtain high-quality solutions from the examined regions. Another remarkable feature of MS-ILS is its simplicity and adaptiveness that ease its implementation. The proposed MS-ILS is tested on G-QMKP benchmark instances derived from the literature. The results indicate that the developed MS-ILS can produce high-quality solutions for the G-QMKP. Particularly, it has been observed that the developed MS-ILS has improved the best known solutions for 35 out of 48 large-size G-QMKP instances.