The quadratic multidimensional knapsack problem: exact, heuristic, and machine learning methods
TL;DR
This work provides a generalizable template for hybrid optimization and learning-based approaches to challenging combinatorial problems and shows that these ML-enhanced hybrid methods improve upon their baseline heuristics and that the genetic algorithm consistently yields near-optimal solutions.
Abstract
This paper presents a multi-faceted approach to solving the quadratic multidimensional knapsack problem (QMDKP), an NP-hard nonlinear combinatorial optimization problem that has received limited attention in the literature. We introduce a new testbed of QMDKP instances with induced profit-weight correlations and evaluate four linearization strategies for solving the problem exactly. To address scalability, we propose several heuristic and metaheuristic methods, including a greedy algorithm, a supervised machine learning (ML)-based approach, and a genetic algorithm. Our underlying ML framework employs binary classification to predict item inclusion probabilities, guiding a greedy construction process. Building on this framework, we explore hybrid strategies such as reduce-fill, expand-repair, and a genetic algorithm with ML-driven repair operators. Extensive computational results show that these ML-enhanced hybrid methods improve upon their baseline heuristics and that the genetic algorithm consistently yields near-optimal solutions. This work provides a generalizable template for hybrid optimization and learning-based approaches to challenging combinatorial problems.