Solución del problema de la mochila 0-1 aplicando un método basado en búsqueda local iterada en la arquitectura obtenida por el cubo

En este trabajo se aborda el Problema de la Mochila 0-1 (KP 0-1). Es un problema de optimización combinatoria, clasificado como un problema NP-Duro. El problema se compone de un conjunto de objetos, cada uno con un peso y un beneficio, el propósito es elegir los objetos que sumen el mayor beneficio sin exceder la capacidad de carga de la mochila. Para este trabajo se utilizan instancias de la literatura clásica y las 7 clases de instancias propuestas por Pisinger (Martello et al., 2000). Se propone un nuevo enfoque para resolver el problema del peso en la mochila 0-1; normalmente para resolver el problema del peso en la mochila 0-1 existen procedimientos que se basan en una búsqueda en el espacio de soluciones factibles de todo el dominio sin conocer su estructura, con tiempos elevados de ejecución, consumiendo demasiados recursos y haciéndolo incomputable en instancias de dimensiones grandes. Con el enfoque propuesto es posible conocer del espacio de soluciones, el cual está dado por el cubo. Este enfoque consiste en utilizar la estructura de un cubo (lattice), que se genera a partir de la unión del conjunto potencia de los objetos de las instancias. La estructura es el cubo de Vladimir Khachaturov basado en un diagrama de Hasse (Khachaturov & Khachaturov, 2007). Para determinar la solución de las instancias, se emplea un método basado en un algoritmo de Búsqueda Local Iterada (ILS) directamente en la estructura, lo que el método hace es buscar en los vértices de la estructura (subconjuntos generados a partir del conjunto potencia) analizando su vecindad evalúa que objeto tiene mayor beneficio, conforme realiza la búsqueda se construye la solucion. La búsqueda se realiza hacia arriba, ya que lo que se busca es maximizar la función objetivo. Para evaluar el desempeño del algoritmo ILS, se realizaron pruebas comparando los resultados de algoritmo Branch and Bound en diferentes instancias; 23 instancias de la literatura, publicadas en Zavala-Díaz et al. 2019, además de 18 instancias de la clase No correlacionadas, 18 instancias de la clase Débilmente correlacionadas, 18 instancias de la clase Fuertemente correlacionadas, publicadas en Zavala-Díaz et al. 2021. Se determinaron soluciones factibles para todas las instancias de prueba, con gran dimensión de hasta 20,000 objetos.