Title: A genetic algorithm combined with mathematical programming to solve generalised quadratic multiple knapsack problem

Authors: Yassine Adouani

Addresses: Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems Laboratory, University of Sfax, Tunisia

Abstract: In this paper, the generalised quadratic multiple knapsack problem (GQMKP) is tackled with an efficient hybrid approach, called GA&IP, which combines a binary genetic algorithm (GA) with integer programming (IP) to solve the GQMKP problem. In the GA&IP approach, a linearisation technique is used to transform the GQMKP into a linear problem called LGQMKP. After that, the LGQMKP is transformed into several dependent classical knapsack problems using a GA. Finally, an IP algorithm is applied to optimally solve each knapsack problem. The effectiveness of the GA&IP approach is demonstrated through experimentation on 96 diverse benchmark instances that are commonly used in the field. Experimental results show the effectiveness of the proposed GA&IP in solving the GQMKP problem and the hybridisation with integer programming can enhance the genetic algorithm.

Keywords: generalised quadratic knapsack problem; genetic algorithm; integer programming.

DOI: 10.1504/IJMOR.2025.148874

International Journal of Mathematics in Operational Research, 2025 Vol.32 No.2, pp.199 - 213

Received: 14 Nov 2023
Accepted: 24 Dec 2023
Published online: 30 Sep 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article