Un algoritmo basado en machine learning para el problema de la mochila multidimensional.
Loading...
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
Esta memoria de título aborda el problema de la mochila multidimensional que es un problema de optimización reconocido por su complejidad y su amplio uso en diferentes áreas. Este es una extensión del problema de la mochila clásico, así que también, busca maximizar el valor total de la cantidad de ítems de la mochila. Esta extensión se diferencia en que agrega el concepto de múltiples dimensiones, y cada una tiene su propia restricción independiente. Este trabajo aborda esta extensión con el objetivo de explorar la mezcla de métodos tradicionales de optimización con machine learning (ML), con el fin de mejorar la eficiencia en el tiempo computacional, tratando de perder la menor calidad de solución posible. Así, el enfoque propuesto consiste en el uso y evaluación de varios modelos de ML, que son integrados con un solver de propósito general para resolver modelos de programación lineal entera. Se intenta usar la predicción de los modelos de ML para analizar las métricas de los ítems y decidir si se considera o no un ítem, buscando alcanzar soluciones de buena calidad en el menor tiempo de cómputo. Se compararon tres versiones. La primera busca ítems candidatos para ser eliminados y luego resolver el problema con el solver. La segunda determina que ítems deben estar en la solución y luego usar esa información antes de resolver. La tercera, basándose en la primera, ajusta los parámetros en la selección para optimizar la decisión, ayudando a descartar una mayor cantidad de ítems. Al compararse, la primera versión mostró un buen desempeño en la identificación de ítems a eliminar y obteniendo buenos resultados tanto calidad de respuesta, como tiempo de cómputo. La segunda versión generó soluciones infactibles, por lo que se descartó. La tercera versión mejoró los resultados obtenidos, acercándose aun más a la solución óptima y con un tiempo menor de cómputo.
El entrenamiento para cada versión se realizó con un amplio conjunto de datos, obtenidos de la literatura, como generados. Aplicando cinco modelos de ML, evaluando los resultados obtenidos en cada uno.
This thesis addresses the multidimensional knapsack problem, a well-known optimization problem recognized for its complexity and broad application across various fields. It is an extension of the classical knapsack problem, also aiming to maximize the total value of the items selected. However, this extension introduces the concept of multiple dimensions, each with its own independent constraint. This work explores this extension with the objective of combining traditional optimization methods with machine learning (ML) to enhance computational efficiency while minimizing the loss of solution quality. The proposed approach involves the use and evaluation of multiple ML models, which are integrated with a general-purpose solver for solving integer linear programming models. The ML models' predictions are leveraged to analyze item metrics and decide whether an item should be considered, aiming to achieve high-quality solutions in the shortest possible computing time. Three versions were compared. The first identifies candidate items for elimination before solving the problem with the solver. The second determines which items must be included in the solution and incorporates that information before solving. The third, based on the first, adjusts selection parameters to optimize decision-making, helping to discard a greater number of items. Upon comparison, the first version performed well in identifying items for elimination, achieving good results in both solution quality and computational time. The second version generated infeasible solutions and was therefore discarded. The third version further improved the results, bringing them closer to the optimal solution while reducing computational time. Training for each version was conducted using an extensive dataset, including both literature-based and generated instances. Five ML models were applied, and the results obtained from each were evaluated.
This thesis addresses the multidimensional knapsack problem, a well-known optimization problem recognized for its complexity and broad application across various fields. It is an extension of the classical knapsack problem, also aiming to maximize the total value of the items selected. However, this extension introduces the concept of multiple dimensions, each with its own independent constraint. This work explores this extension with the objective of combining traditional optimization methods with machine learning (ML) to enhance computational efficiency while minimizing the loss of solution quality. The proposed approach involves the use and evaluation of multiple ML models, which are integrated with a general-purpose solver for solving integer linear programming models. The ML models' predictions are leveraged to analyze item metrics and decide whether an item should be considered, aiming to achieve high-quality solutions in the shortest possible computing time. Three versions were compared. The first identifies candidate items for elimination before solving the problem with the solver. The second determines which items must be included in the solution and incorporates that information before solving. The third, based on the first, adjusts selection parameters to optimize decision-making, helping to discard a greater number of items. Upon comparison, the first version performed well in identifying items for elimination, achieving good results in both solution quality and computational time. The second version generated infeasible solutions and was therefore discarded. The third version further improved the results, bringing them closer to the optimal solution while reducing computational time. Training for each version was conducted using an extensive dataset, including both literature-based and generated instances. Five ML models were applied, and the results obtained from each were evaluated.
Description
Tesis presentada para optar al título de Ingeniero Civil Industrial
Keywords
Inteligencia artificial, Optimización combinatoria, Machine Learning