Acerca de una versión dinámica del problema de la mochila

Resumen

El problema de la mochila (Knapsack Problem, KP) es un problema clásico de optimización combinatoria que ha sido ampliamente estudiado por más de un siglo. Es uno de los problemas de programación lineal entera más simples; aparece como subproblema en otros problemas más complejos; y tiene muchas aplicaciones prácticas, en áreas tan diversas como el corte de material, la selección de inversiones de capital y portafolios financieros, la correcta administración de recursos de cómputo, del ancho de banda de una conexión, del espacio de almacenamiento en discos duros, etc. Variantes dinámicas de este problema han sido estudiadas por sus aplicaciones prácticas, aunque no en gran extensión y con pocos resultados obtenidos hasta el presente. La variante considerada en este artículo consiste en agregar una dimensión temporal (discreta) al problema clásico: a cada objeto se le asigna una duración, que indica el intervalo de tiempo que éste debe permanecer dentro de la mochila cada vez que es seleccionado. Se busca maximizar el valor total almacenado en la mochila dentro de un horizonte temporal. Formulamos un modelo de programación lineal entero para este problema y presentamos un algoritmo de solución exacto basado en el esquema branch-and-bound. Adicionalmente, estudiamos su comportamiento y su desempeño computacional.

 

Abstract: The Knapsack Problem (KP) is a classical combinatorial optimization problem that has been widely studied for more than a hundred years (see, for a example [12] and the references there in). It is one of the simplest linear integer programming problems and appears as a subproblem in other more complex problems. It has many practical applications in such diverse areas as cutting-stock [6]; investment selection in capital and financial portfolios [10]; the correct administration of a computer RAM memory, band-width of a connection, disk space [14], etc. Dynamic variants of this problem have been studied for their practical applications, although not in a wide extension and with few results reported up to the present. In this paper we consider a variant which consists in adding a (discrete) temporal dimensión to the classic problem: a duration is assigned to each object indicating the interval of time that it has to remain inside the knapsack whenever it is chosen. The objective is to maximize the total value stored in the knapsack within a certain temporal horizon T. We formulate an integer programming model for this problem and develop an exact solution algorithm based on the branch-and-bound scheme. Furthermore, we report results on its computational behavior and performance.