Una matheurística para la resolución del Set Union Knapsack Problem.

Abstract

El Set Union Knapsack Problem (SUKP) es una generalización del problema de la mochila (KP) clásica, donde el objetivo es seleccionar desde un conjunto de ítems que aportan beneficio, aquellos que maximizan este último, sujeto a una restricción de capacidad. En el caso del SUKP, estos ítems se forman por elementos que son los que ocupan capacidad. Esta característica convierte al SUKP en un problema de complejidad mayor al KP clásico, esto último sumado a las múltiples aplicaciones en sistemas de producción, finanzas, bases de datos, entre otras, otorgan gran relevancia a la investigación de este problema. En este trabajo se presenta una matheurística para la resolución del SUKP, que utiliza soluciones parciales creada mediante muestreo aleatorio, generando instancias reducidas que luego son resultas mediante CPLEX y/o MSBTS, algoritmo del estado del arte dedicado a resolver el SUKP. Se realiza una revisión de la literatura del estado del arte de los métodos para resolver el SUKP. Se reportan resultados computacionales sobre 30 instancias ejecutadas, siendo estos resultados comparados con otros algoritmos del estado del arte. Los resultados muestran un buen desempeño del algoritmo propuesto, muchas veces cercano a los métodos de vanguardia,destacando una brecha de rendimiento menor al 0.5% en el mejor valor encontrado para la función objetivo.