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

作     者：Yanez-Oyarce, Diego Contreras-Bolton, Carlos Troncoso-Espinosa, Fredy Rey, Carlos 

作者机构：Univ Bio Bio Dept Ingn Ind Concepcion 3780000 Chile Univ Concepcion Dept Ingn Ind Concepcion 4070409 Chile 

出 版 物：《IEEE ACCESS》 (IEEE Access)

年 卷 期：2025年第13卷

页      面：10638-10652页

核心收录：

基　　金：Subvencion a la Instalacion en la Academia Vicerrectoria deInvestigacion y Postgrado (UBB-VRIP) through the ''Proyecto de Investigacion Interno 2023'' [RE2360219] National Agency for Research and Development (ANID) through the FONDECYT Iniciacion 

主　　题：Classification algorithms Prediction algorithms Metaheuristics Genetic algorithms Synthetic data Heuristic algorithms Correlation Support vector machines Standards Mathematical models Machine learning combinatorial optimization knapsack problem 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.