Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem

The quadratic multiple knapsack problem (QMKP) is a well-studied problem in operations research. This problem involves selecting a subset of items that maximizes the linear and quadratic profit without exceeding a set of capacities for each knapsack. While its solution using metaheuristics has been explored, exact approaches have recently been investigated. One way to improve the performance of these exact approaches is by reducing the solution space in different instances, considering the properties of the items in the context of QMKP. In this paper, machine learning (ML) models are employed to support an exact optimization solver by predicting the inclusion of items with a certain level of confidence and classifying them. This approach reduces the solution space for exact solvers, allowing them to tackle more manageable problems. The methodological process is detailed, in which ML models are generated and the best one is selected to be used as a preprocessing approach. Finally, we conduct comparison experiments, demonstrating that using a ML model is highly beneficial for reducing computing times and achieving rapid convergence.