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

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.