Una metaheurística para resolver el polynomial robust knapsack problem.

Abstract

El polynomial robust knapsack problem (PRKP) es una variante del clásico knapsack problem (KP), que consiste en elegir un subconjunto de elementos que maximice la utilidad, sujetos a restricciones de capacidad. En el contexto del PRKP, los elementos exhiben un beneficio independiente y uno dependiente de otros elementos seleccionados, denominado sinergía. Esto refleja situaciones del mundo real, tales como la construcción de un estacionamiento al lado de una estación de metro concurrida, proyectos que se benefician mutuamente. Además, los costos asociados a la elección de cada elemento son inciertos y varían en un rango determinado. Esta característica confiere al PRKP una complejidad superior en comparación con el KP tradicional. Dada su aplicabilidad en diversos campos, especialmente en inversiones, la investigación de este problema adquiere gran relevancia. Por tanto, esta memoria de título presenta una heurística para abordar la resolución del PRKP. Se propone una metodología que emplea soluciones parciales generadas mediante un muestreo aleatorio, generando instancias de menor envergadura que son posteriormente resueltas mediante el empleo de un solver de propósito general. El algoritmo propuesto es validado en 1600 instancias y se comparan con otros algoritmos del estado del arte. Los resultados indican un rendimiento competitivo, en muchos casos aproximándose a las soluciones obtenidas por los métodos de la literatura. Cabe mencionar que se obtiene una diferencia de valor obtenido para la función objetivo, igual o inferior al 5% en comparación con el solver de propósito general.

The polynomial robust knapsack problem (PRKP) is a variant of the classic knapsack problem (KP), which involves choosing a subset of elements to maximize utility, subject to capacity constraints. In the context of PRKP, elements exhibit both independent and dependent benefits on other selected elements, known as synergy. This reflects real-world situations, such as building a parking lot next to a busy subway station, where projects mutually benefit each other. Additionally, the costs associated with choosing each element are uncertain and vary within a specified range. This characteristic adds complexity to PRKP compared to the traditional KP. Due to its applicability in various fields, particularly in investments, researching this problem becomes highly relevant. Therefore, this thesis presents a heuristic to address the resolution of PRKP. A methodology is proposed that uses partial solutions generated through random sampling, creating smaller instances that are subsequently solved using a general-purpose solver. The proposed algorithm is validated on 1600 instances and compared with other state-of-the-art algorithms. The results indicate competitive performance, in many cases approaching to the results obtained by the methods of the state-of-the-art. It is worth mentioning that a difference in the objective function value is obtained, equal to or less than 5%, compared to the general-purpose solver.