El problema de la mochila multidimensional (MKP). Métodos de solución y aplicación a problemas de selección de proyectos

Abstract

En este trabajo fin de grado se realiza un estudio teórico sobre los diferentes problemas MKP (multidimensional knapsack problem), junto con un desarrollo práctico en el que se implementan diferentes algoritmos para la resolución de dichos problemas. Para la aplicación práctica de dicho trabajo se utilizarán los datos de la librería ORLIB http://people.brunel.ac.uk la cual cuenta con una serie de problemas MKP los cuales están resueltos en varios artículos que tratan este tema. Además, se ha construido un algoritmo para la lectura de dichos datos de forma que podamos identificar y seleccionar de manera correcta los datos del problema. Finalmente se ha realizado una comparación entre los diferentes algoritmos utilizados para determinar cuál de ellos tiene un mejor funcionamiento dependiendo del tamaño del problema y las características del mismo.

In this final degree thesis a theoretical study of the different MKP (multidimensional knapsack problem) problems is carried out, together with a practical development in which different algorithms are implemented for the resolution of these problems. For the practical application of this work, data from the ORLIB library http://people.brunel.ac.uk will be used, which has a series of MKP problems that have been solved in several articles on this subject. In addition, an algorithm for reading the data has been constructed so that we can identify and select the data of the problem correctly. Finally, a comparison has been made between the different algorithms used to determine which of them performs better depending on the size of the problem and the characteristics of the problem.