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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10839359/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832592947219005440 |
|---|---|
| author | Diego Yanez-Oyarce Carlos Contreras-Bolton Fredy Troncoso-Espinosa Carlos Rey |
| author_facet | Diego Yanez-Oyarce Carlos Contreras-Bolton Fredy Troncoso-Espinosa Carlos Rey |
| author_sort | Diego Yanez-Oyarce |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-ae95ec41b0864b2ea67d09a16e23694f |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-ae95ec41b0864b2ea67d09a16e23694f2025-01-21T00:01:16ZengIEEEIEEE Access2169-35362025-01-0113106381065210.1109/ACCESS.2025.352931710839359Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack ProblemDiego Yanez-Oyarce0https://orcid.org/0009-0004-6468-5632Carlos Contreras-Bolton1https://orcid.org/0000-0001-9549-4143Fredy Troncoso-Espinosa2https://orcid.org/0000-0002-9972-3123Carlos Rey3https://orcid.org/0009-0000-0884-7423Departamento de Ingeniería Industrial, Universidad del Bío-Bío, Concepción, ChileDepartamento de Ingeniería Industrial, Universidad de Concepción, Concepción, ChileDepartamento de Ingeniería Industrial, Universidad del Bío-Bío, Concepción, ChileDepartamento de Ingeniería Industrial, Universidad del Bío-Bío, Concepción, ChileThe 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.https://ieeexplore.ieee.org/document/10839359/Machine learningcombinatorial optimizationknapsack problemquadratic multiple knapsack problem |
| spellingShingle | Diego Yanez-Oyarce Carlos Contreras-Bolton Fredy Troncoso-Espinosa Carlos Rey Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem IEEE Access Machine learning combinatorial optimization knapsack problem quadratic multiple knapsack problem |
| title | Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem |
| title_full | Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem |
| title_fullStr | Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem |
| title_full_unstemmed | Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem |
| title_short | Machine Learning-Driven Optimization for Solution Space Reduction in the Quadratic Multiple Knapsack Problem |
| title_sort | machine learning driven optimization for solution space reduction in the quadratic multiple knapsack problem |
| topic | Machine learning combinatorial optimization knapsack problem quadratic multiple knapsack problem |
| url | https://ieeexplore.ieee.org/document/10839359/ |
| work_keys_str_mv | AT diegoyanezoyarce machinelearningdrivenoptimizationforsolutionspacereductioninthequadraticmultipleknapsackproblem AT carloscontrerasbolton machinelearningdrivenoptimizationforsolutionspacereductioninthequadraticmultipleknapsackproblem AT fredytroncosoespinosa machinelearningdrivenoptimizationforsolutionspacereductioninthequadraticmultipleknapsackproblem AT carlosrey machinelearningdrivenoptimizationforsolutionspacereductioninthequadraticmultipleknapsackproblem |