A Hybrid Machine Learning–Metaheuristic Approach to Solving the Quadratic Multidimensional Knapsack Problem

The quadratic multidimensional knapsack problem (QMdKP) is a combinatorial optimization problem that involves selecting a subset of items to maximize both linear and quadratic profits without exceeding the capacity constraints across multiple dimensions. Due to its NP-hard nature, this paper presents a framework that integrates machine learning to mitigate the high computational cost associated with its resolution. The proposed methodology employs a classification model to predict item inclusion in the optimal solution prior to the optimization process, effectively reducing the number of decision variables handled by the solver. Additionally, to address large-scale instances, we propose an iterated local search metaheuristic initialized via the predictive algorithm. These strategies were benchmarked against a standard solver, demonstrating their capability of finding optimal or near-optimal solutions with execution time improvements of up to 83%.