Algoritmos de solución para una versión dinámica del problema de la mochila

Abstract

El problema de la mochila (Knapsack Problem, KP) es un problema 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, tales como encontrar patrones de corte de material que generen el menor desperdicio posible; en la selección de inversiones de capital y portafolios financieros; en la correcta administración de recursos de memoria RAM de una computadora, del ancho de banda de una conexión, del espacio en disco, etc. En el problema clásico de la mochila, se tienen n objetos y una mochila de capacidad de almacenamiento C. Cada objeto tiene un valor y peso asignados y, se pide encontrar un subconjunto de objetos cuya suma de valores sea máxima y cuya suma de pesos no sobrepase la capacidad C. Variantes dinámicas de este problema clásico de optimización combinatoria han sido estudiadas por sus aplicaciones prácticas, aunque no en gran extensión y con pocos resultados obtenidos hasta el presente. Una de estas variantes es la de 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 considera un horizonte temporal T y se pide maximizar el valor total almacenado en la mochila en el intervalo [0,T].