ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA

Acerca De Una Versión Dinámica Del Problema De La Mochila

Silva Bruno*; Torres Luis M.**

*Escuela Politécnica Nacional, Facultad de Ciencias, Quito, Ecuador

e-mail: [Link] [Link]
**Escuela Politécnica Nacional, Centro de Modelización Matemática ModeMat, Quito, Ecuador
e-mail: [Link] [Link]
Resumen: El problema de lamochila (Knapsack Problem, KP) es un problema clásico de optimización
combinatoria que ha sido ampliamente estudiado por más de un siglo (ver, por ejemplo [12] y las referencias allí
citadas). 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 como: el corte de material [6], la selección de
inversiones de capital y portafolios financieros [10], la correcta administración de recursos de cómputo, del ancho
de banda de una conexión, del espacio de almacenamiento en discos duros [14], 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 T. Formulamos un modelo de programación lineal entera 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.

Palabras clave: problema de la mochila (knapsack problem), optimización dinámica, branch-and-bound,

heurísticas primales.

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.

Keywords: knapsack problem, dynamic optimization, branch-and-bound, primal heuristics.

1 𝑛

𝑚𝑎𝑥 𝑝𝑖 𝑥𝑖
1. INTRODUCCION 𝑖=1
𝑛
𝐾𝑃 =
Dados una mochila con capacidad C y un conjunto de n 𝑠. 𝑡 𝑤𝑖 𝑥𝑖 ≤ 𝐶,
objetos diferentes, con valores p1, ...pn y tamaños w1, ..., wn, 𝑖=1
el problema clásico de la mochila (Knapsack Problem - KP) 𝑥𝑖 ∈ 0,1 , ∀𝑖 ∈ {1, … , 𝑛}
consiste en seleccionar un subconjunto de objetos (para
almacenarlos en la mochila) cuya suma de tamaños no supere El problema de la mochila es un problema clásico en la
C y cuya suma de valores sea la mayor posible. optimización combinatoria. Constituye uno de los problemas
más simples de la programación lineal entera, aparece como
Introduciendo para cada objeto una variable binaria xi, 1 ≤ i ≤ subproblema en muchos otros problemas más complejos y
n, que indique si el mismo debe ser incluido o no en la tiene diversas aplicaciones prácticas. Diferentes técnicas de
selección, el problema puede formularse como un programa solución han sido abordadas durante las últimas décadas. En
de optimización lineal entera: 1957, Dantzig [4] presentó un método eficiente para
determinar la solución de la relajación continua del problema
(CKP), y por lo tanto, una cota superior para el problema
discreto. En 1967, Kolesar propuso el primer algoritmo tipo

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
2

branch-and-bound para KP. Durante los años 70’s, los autores denotan a la variante del problema como problema
métodos tipo branch-andbound se desarrollaron más, gracias temporal de la mochila (TKP, temporal knapsack problem).
a lo cual fue posible resolver problemas con un gran número
de variables. El algoritmo más conocido de este período se En la variante dinámica que consideramos en este artículo,
debe a Horowitz y Sahni [7]. En 1977Martello y Toth [11] los n objetos tienen asociados, además de valores y tamaños,
propusieron la primera cota superior que mejora el valor de la duraciones d1, ..., dn. Esto significa que si el objeto i es
relajación continua CKP. En la década de los 80’s los agregado a la mochila en el tiempo t, el mismo permanecerá
resultados tienen que ver con la solución de problemas de dentro de la misma hasta el tiempo t + di − 1.
gran tamaño. Balas y Zemel [2] presentaron un nuevo
enfoque para resolver el problema clasificando, en muchos El objetivo del problema es maximizar el valor total
casos, solo un subconjunto pequeño de las variables. Desde almacenado en la mochila dentro de un horizonte temporal.
esta época en adelante se empezaron a estudiar variantes de Presentamos un modelo de programación lineal entera para
este problema tales como su versión acotada, no-acotada y el este problema, estudiamos cotas superiores, heurísticas
problema de la mochila de elección múltiple. Martello y Toth primales y proponemos un algoritmo de solución basado en
publicaron en 1990 una revisión exhaustiva de los diferentes el esquema branch-and-bound. Finalmente, presentamos
resultados teóricos y métodos de solución existentes hasta ese resultados comparativos del desempeño computacional de
momento [12]. una implementación de nuestro algoritmo frente al solver
SCIP [1] para problemas lineales enteros. Los resultados
Desde el enfoque de la teoría de complejidad computacional, completos del presente trabajo han sido publicados en [16].
el problema de la mochila pertenece a la clase de problemas
NP-difíciles (ver detalles de la definición de esta clase, por
ejemplo, en [5, p. 247]), para los cuales suele asumirse que
no existen algoritmos polinomiales de solución (a menos que 2. EL PROBLEMA KP-DUR
P=NP). Para demostrar esto, basta notar que KP es una 2.1 Modelo de programación entera
generalización del problema SUBSET-SUM (que es uno de
los problemas NP-completos estándares [8]): dados un Como se señaló anteriormente, en esta variante del problema
conjunto finito A = {a1, ..., an} de números enteros, y un se tienen dados una mochila con capacidad C y un conjunto
número B ∈ Z, determinar si existe un subconjunto A′ ⊆ A tal de n objetos los cuales tienen asociados valores p1, ..., pn,
que 𝑎𝑖∈𝐴′ 𝑎𝑖 = 𝐵. tamaños w1, ..., wn y duraciones d1, ..., dn. El objetivo es
maximizar el valor total almacenado en la mochila dentro de
En efecto, puede verse que toda instancia de SUBSET- un intervalo de tiempo, el mismo que consideraremos
SUMpuede transformarse en una instancia de KP con n discretizado en períodos {1, 2, ..., T}. Si el objeto i ingresa en
objetos, cuyos pesos y valores están dados por wi = pi = ai, y la mochila en el período t ∈ {1, ..., T − di − 1}, permanecerá
donde la capacidad de la mochila es igual a B. Por otra parte, en la misma hasta el período t + di + 1. Asumimos que todos
puede considerarse a KP como uno de los problemas “más los parámetros C, T, pi, wi y di son enteros, y que un objeto
fáciles” dentro de la clase NP-difícil, pues existen para este puede ingresar más de una vez en la mochila.
problema esquemas de aproximación eficientes (PTAS [17] y
FPTAS [9]). Definimos variables binarias xit, i ∈ {1, ..., n}, t ∈ {1, ..., T},
que nos indican si el objeto i ingresa en la mochila en el
El KP aparece en aplicaciones prácticas en procesos de toma período t; y variables binarias zit, i ∈ {1, ..., n}, t ∈ {1, ..., T},
de decisiones del mundo real, tales como la búsqueda de que nos indican si el objeto i se encuentra presente en la
patrones de corte para materias primas que generen el menor mochila en el período t. De esta manera, el problema puede
desperdicio posible [6], la selección de inversiones de capital formularse como el siguiente programa de optimización
y portafolios financieros [10] y la optimización de recursos entera (KP-DUR*):
computacionales [14]. Se han estudiado algunas variantes
dinámicas del problema de la mochila. Por ejemplo, 𝑛 𝑇

Papastavrou [13] considera una situación en la cual los 𝑚á𝑥 𝑝𝑖 𝑥𝑖𝑡 (1)
objetos arriban de acuerdo a un proceso de Poisson en el 𝑖=1 𝑡
𝑛
tiempo. Cada objeto tiene asociados una demanda de un
recurso limitado y un valor. Cuando un objeto arriba, debe 𝑠. 𝑡 𝑤𝑖 𝑧𝑖𝑡 ≤ 𝐶, ∀𝑡 ∈ 1, … , 𝑇 , (2)
𝑖=1
decidirse si el mismo es aceptado o rechazado. El objetivo es
𝑥𝑖𝑡 = 0, ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 𝑇 − 𝑑𝑖 + 2, … , 𝑇 (3)
diseñar una estrategia óptima para maximizar el valor
𝑥𝑖𝑡 = 1 ⟹ 𝑧𝑖,𝑡+1 = 1, ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑙 ∈ 0, … , 𝑑𝑖 − 1 (4)
acumulado esperado, correspondiente a los objetos aceptados
𝑥𝑖𝑡 = 1 ⟹ 𝑥𝑖,𝑡+1 = 0, ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑙 ∈ 1, … , 𝑑𝑖 − 1 (5)
dentro de un horizonte de tiempo. En otro contexto, Bartlett 𝑚𝑖𝑛 {𝑑 𝑖 −1,𝑡−1}
et al. [3] consideran el problema de calendarizar la asignación
de un recurso compartido para atender un conjunto de 𝑧𝑖𝑡 ≤ 𝑥𝑖,𝑡−𝑙 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑇 (6)
𝑙=0
pedidos, cada uno de los cuales tiene un tiempo de inicio, un
𝑥𝑖𝑡 , 𝑧𝑖𝑡 ∈ 0,1 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑇
tiempo de finalización y un monto solicitado del recurso. Los

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
3

La función objetivo (1) mide el valor total de los objetos que variables zit, xit, yit y pueden verse como restricciones de
ingresan en la mochila dentro del horizonte de tiempo {1, ..., balance: si el objeto i entra en la mochila en el período t
T}. Las restricciones (2) sirven para asegurar que en cada entonces el valor de zit aumenta (con relación al valor de
período la capacidad de la mochila sea respetada. La zi,t−1). Si el objeto sale de la mochila, el valor de zit
restricciones (3) impiden que un objeto ingrese en la mochila disminuye. En todos los demás casos, el valor de zit
demasiado tarde, es decir, si su tiempo de permanencia permanece inalterado.
previsto excede el horizonte de tiempo T. La restricciones (4)
establecen que si un objeto i ingresa a la mochila, entonces En [16] se demuestra que las formulaciones KP-DUR y KP-
este objeto permanece en la misma durante di unidades de DUR* son equivalentes entre sí. En adelante describiremos
tiempo. Las restricciones (5) aseguran que ningún objeto el esquema general de la demostración. Para los detalles (y
pueda volver a entrar en la mochila hasta que no haya salido las demostraciones de los lemas intermedios), referimos al
de ella. Finalmente, las restricciones (6) expresan que un lector al documento de la tesis. Notaremos como FIP al
objeto no puede estar en la mochila en un período t sin haber conjunto de todas las soluciones factibles de un problema de
ingresado a ésta en ninguno de los períodos anteriores {t, t−1, optimización IP. Para los dos problemas anteriores, tenemos
..., t−di+1}. Esta formulación del problema es simple y los conjuntos FKP-DUR∗ y FKP-DUR, cuyas propiedades
directa, pero no es adecuada para el desarrollo de algoritmos estudiaremos a continuación. Se establecen primero los
de solución. Entre otras dificultades, no todas las familias de siguientes resultados auxiliares para KP-DUR:
restricciones son lineales, pues en el caso de (4) y (5) se trata
de implicaciones lógicas. Por este motivo, hemos 𝐋𝐄𝐌𝐀 𝟏 𝟏𝟔 . 𝑆𝑒𝑎 𝑥, 𝑦, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 .
considerado una formulación alternativa, la misma que se ∀𝑖 ∈ 1, … , 𝑛 , 𝑡 ∈ 1, … , 𝑇 − 𝑑𝑖 + 1 𝑠𝑖 𝑥𝑖𝑡 = 1 ⇒
describe a continuación. 𝑧𝑖,𝑡+1 = 1, ∀𝑙 ∈ 0, … , 𝑑𝑖 − 1 .
∀𝑖 ∈ 1, … , 𝑛 , 𝑡 ∈ 1, … , 𝑇 − 𝑑𝑖 + 1 𝑠𝑖 𝑥𝑖𝑡 = 1 ⇒
Nuevamente, definimos variables binarias xit, i ∈ {1, ..., n},
𝑥𝑖,𝑡+1 = 0, ∀𝑙 ∈ 0, … , 𝑑𝑖 − 1 .
t ∈ {1, ..., T}, que nos indican si el objeto i ingresa en la
mochila en el período t y variables binarias zit, i ∈ {1, ..., n}, 𝐋𝐄𝐌𝐀 𝟐 𝟏𝟔 . 𝑆𝑒𝑎 𝑥, 𝑦, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 . 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠
𝑚𝑖𝑛{𝑑𝑖 −1,𝑡−1}
t ∈ {1, ..., T}, que nos indican si el objeto i está en la mochila
en el período t. Además, introducimos variables binarias yit, 𝑧𝑖𝑡 ≤ 𝑥𝑖,𝑡 − 𝑙 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑇
i ∈ {1, ..., n}, t ∈ {1, ..., T}, que nos indican si el objeto i sale 𝑙=0
de la mochila en el período t.
De los dos lemas anteriores podemos concluir el siguiente
El modelo (KP-DUR) se formula de la siguiente manera: corolario.

𝑛 𝑇 𝐂𝐎𝐑𝐎𝐋𝐀𝐑𝐈𝐎 𝟏. 𝑆𝑖 𝑥, 𝑦, 𝑧 ∈ , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑥, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 ∗.

𝑚á𝑥 𝑝𝑖 𝑥𝑖𝑡 (7) 𝐴𝑑𝑒𝑚á𝑠, 𝑛𝑜𝑡𝑎𝑟 𝑞𝑢𝑒 𝑎𝑚𝑏𝑎𝑠 𝑠𝑜𝑙𝑢𝑐𝑖𝑜𝑛𝑒𝑠 𝑛𝑎𝑙𝑐𝑎𝑛𝑧𝑎𝑛 𝑒𝑙
𝑖=1 𝑡 𝑚𝑖𝑠𝑚𝑜 𝑣𝑎𝑙𝑜𝑟 𝑒𝑛 𝑙𝑎 𝑓𝑢𝑛𝑐𝑖ó𝑛 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜
𝑛

𝑠. 𝑡 𝑤𝑖 𝑧𝑖𝑡 ≤ 𝐶, ∀𝑡 ∈ 1, … , 𝑇 , 8 Para el sentido inverso de la equivalencia, requerimos de los

𝑖=1 siguientes resultados.
𝑦𝑖𝑡+𝑑 = 𝑥𝑖𝑡 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑇 − 𝑑𝑖 , 9
𝑖
𝐋𝐄𝐌𝐀 𝟑 𝟏𝟔 . 𝑆𝑒𝑎 𝑥, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 ∗. 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠
𝑥𝑖𝑡 = 0, ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 𝑇 − 𝑑𝑖 + 2, … , 𝑇 , (10) 𝑚𝑖𝑛{𝑑𝑖 −1,𝑡−1}
𝑦𝑖𝑡 = 0, ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑑𝑖 (11)
𝑧𝑖𝑡 ≤ 𝑥𝑖,𝑡−𝑙 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑇
𝑧𝑖1 = 𝑥𝑖1 , ∀𝑖 ∈ 1, … , 𝑛 (12)
𝑙=0
𝑧𝑖𝑡 = 𝑧𝑖,𝑡−1 + 𝑥𝑖𝑡 − 𝑦𝑖𝑡 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 2, … , 𝑇 , (13) 𝐋𝐄𝐌𝐀 𝟒 𝟏𝟔 . 𝑆𝑒𝑎 𝑥, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 ∗. 𝐷𝑒𝑓𝑖𝑛𝑖𝑚𝑜𝑠
𝑥𝑖𝑡 , 𝑦𝑖𝑡 , 𝑧𝑖𝑡 ∈ 0,1 , ∀𝑖 ∈ 1, … , 𝑛 , ∀𝑡 ∈ 1, … , 𝑇 𝑦 ∈ 0,1 𝑛×𝑇 𝑝𝑜𝑟 𝑚𝑒𝑑𝑖𝑜 𝑑𝑒:
0, 𝑠𝑖 𝑡 = 1,
La función objetivo (7) mide el valor total de los objetos 𝑦𝑖𝑡 = 𝑧 + 𝑥 − 𝑧 𝑠𝑖 𝑡 ∈ {2, … , 𝑇}
𝑖,𝑡−1 𝑖𝑡 𝑖𝑡
ingresados en la mochila dentro del horizonte de tiempo {1, 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑥, 𝑦, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 . 𝑁𝑜𝑡𝑎𝑟 𝑎𝑑𝑒𝑚á𝑠 𝑞𝑢𝑒 𝑙𝑜𝑠
..., T}. Las restricciones (8) sirven para asegurar que en cada 𝑣𝑎𝑙𝑜𝑟𝑒𝑠𝑑𝑒 𝑙𝑎𝑠 𝑓𝑢𝑛𝑐𝑖𝑜𝑛𝑒𝑠 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜 𝑝𝑎𝑟𝑎 𝑎𝑚𝑏𝑎𝑠 𝑠𝑜𝑙𝑢𝑐𝑖𝑜𝑛𝑒𝑠
período la capacidad de la mochila sea respetada, las
restricciones (9) establecen que si el objeto i ingresa a la 𝑐𝑜𝑖𝑛𝑐𝑖𝑑𝑒𝑛
mochila, entonces este objeto debe salir de la misma luego de
di unidades de tiempo. Las restricciones (10) impiden que un En el Corolario 1 y el Lema 4 hemos demostrado que PDUR
objeto ingrese en la mochila si su duración prevista excede el y KP-DUR* son dos formulaciones equivalentes del mismo
horizonte de tiempo T. De manera recíproca, las restricciones problema. Se tiene además el siguiente resultado para KP-
(11) impiden que un objeto salga de la mochila en los di UR*, que emplearemos posteriormente.
períodos iniciales ya que esto no tiene sentido práctico. Las
restricciones (12) y (13) especifican la relación entre las

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
4

𝐋𝐄𝐌𝐀 𝟓 𝟏𝟔 . 𝑆𝑒𝑎 𝑥, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 ∗. 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 La relación entre KP-PD y KP-DUR está establecida en el
𝑇 𝑇
siguiente resultado.
𝑧𝑖𝑡 = 𝑑𝑖 𝑥𝑖𝑡 , ∀𝑖 ∈ 1, … , 𝑛 .
𝑙=1 𝑙=1 𝐋𝐄𝐌𝐀 𝟕 𝟏𝟔 . 𝑆𝑒𝑎 𝑥, 𝑦, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 . 𝑦 𝑠𝑒𝑎𝑛
Del Lema 4 se sigue además que:
𝑥 1 , … , 𝑥 𝑇 ∈ 0,1 𝑛 𝑑𝑒𝑓𝑖𝑛𝑖𝑑𝑜𝑠 𝑝𝑜𝑟 𝑥𝑖𝑡 = 𝑧𝑖𝑡 , 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑡 ∈
𝐂𝐎𝐑𝐎𝐋𝐀𝐑𝐈𝐎 𝟐. 𝑆𝑒𝑎 𝑥, 𝑦, 𝑧 ∈ ℱ𝐾𝑃−𝐷𝑈𝑅 . 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 1, … , 𝑇 , 𝑖 ∈ 1, … , 𝑛 . 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑥 𝑡 ∈ ℱ𝐾𝑃−𝑃𝐷, ∀𝑡
𝑇 𝑇 ∈ {1, … , 𝑇}.
𝑧𝑖𝑡 = 𝑑𝑖 𝑥𝑖𝑡 , ∀𝑖 ∈ 1, … , 𝑛 .
𝑙=1 𝑙=1 En otras palabras, para cada período t ∈ {1, ..., T}, la
solución de KP-DUR restringida a t es una solución factible
para KP-PD. Por otra parte, sean (x, y, z) ∈ FKP-DUR una
2.2 Cotas superiores e inferiores solución óptima para una instancia de KP-DUR y x ∗ ∈
FKP−PD una solución óptima para la instancia
correspondiente de KP-PD. Tenemos entonces que para el
Presentamos a continuación dos formulaciones del problema valor objetivo de estas soluciones se cumple,
clásico de la mochila que pueden emplearse para obtener
cotas superiores al valor óptimo de KP-DUR. 𝑛 𝑇 𝑛 𝑇

𝑝𝑖 𝑥𝑖𝑡 = 𝑝𝑖 𝑥𝑖𝑡
𝑛
𝑖=1 𝑡=1 𝑖=1 𝑡=1
𝑚á𝑥 𝑝𝑖 𝑦𝑖 𝑛 𝑇
𝑡=1 𝑧𝑖𝑡
𝑖=1 𝑝𝑖 , 𝑝𝑜𝑟 𝑒𝑙 𝑐𝑜𝑟𝑜𝑙𝑎𝑟𝑖𝑜 2
𝑛 𝑑𝑖
𝑖=1
(𝐾𝑃 − 𝐶𝑇) 𝑠. 𝑡 (𝑤𝑖 𝑑𝑖 )𝑦𝑖 ≤ 𝐶𝑇,
𝑛 𝑇
𝑝𝑖
= 𝑧𝑖𝑡 ,
𝑖=1 𝑑𝑖
𝑇 𝑖=1 𝑡=1
0 ≤ 𝑦𝑖 ≤ , 𝑦𝑖 ∈ ℕ, ∀𝑖 ∈ {1, … , 𝑛} 𝑛
𝑝𝑖
𝑇
𝑑𝑖 = 𝑥𝑖𝑡 ,
𝑑𝑖
𝑖=1 𝑡=1
𝑇 𝑛 𝑛
𝑝𝑖 ∗ 𝑝𝑖 ∗
≤ 𝑥 =𝑇 𝑥
Este problema tiene la forma de una de las generalizaciones 𝑑𝑖 𝑖 𝑑𝑖 𝑖
𝑡=1 𝑖=1 𝑖=1
del problema clásico de la mochila, específicamente de la
versión acotada BKP.
donde 𝑥 𝑡 son las soluciones factibles para KP-PD definidasen
el Lema 7. Por lo tanto, hemos demostrado el siguiente
La capacidad de la mochila es igual a CT, el tamaño del resultado:
𝑇
objeto i es widi y la cantidad disponible del mismo es .
𝑑𝑖
Hemos demostrado que KP-CT puede verse como una 𝐋𝐄𝐌𝐀 𝟖 𝟏𝟔 . 𝑈𝑛𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 ó𝑝𝑡𝑖𝑚𝑎 𝑥 ∗ 𝑑𝑒 𝑢𝑛𝑎 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑖𝑎
relajación de KP-DUR: 𝑑𝑒 𝐾𝑃 − 𝑃𝐷 𝑝𝑒𝑟𝑚𝑖𝑡𝑒 𝑑𝑒𝑓𝑖𝑛𝑖𝑟 𝑙𝑎 𝑠𝑖𝑔𝑢𝑖𝑒𝑛𝑡𝑒 𝑐𝑜𝑡𝑎 𝑠𝑢𝑝𝑒𝑟𝑖𝑜𝑟
𝑝𝑎𝑟𝑎 𝑙𝑎 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑖𝑎 𝑑𝑒 𝐾𝑃 − 𝐷𝑈𝑅:
𝐋𝐄𝐌𝐀 𝟔 𝟏𝟔 . 𝐷𝑎𝑑𝑎 𝑢𝑛𝑎 𝑓𝑢𝑛𝑐𝑖ó𝑛 𝑓𝑎𝑐𝑡𝑖𝑏𝑙𝑒 𝑥, 𝑦, 𝑧 ∈
ℱ𝐾𝑃−𝐷𝑈𝑅 , 𝑒𝑠 𝑝𝑜𝑠𝑖𝑏𝑙𝑒 𝑑𝑒𝑓𝑖𝑛𝑖𝑟 𝑢𝑛𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑦 ∈ ℱ𝐾𝑃−𝐶𝑇, 𝑛
𝑝𝑖 ∗
𝑡𝑎𝑙 𝑞𝑢𝑒 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜𝑠 𝑑𝑒 𝑎𝑚𝑏𝑎𝑠 𝑠𝑜𝑙𝑢𝑐𝑖𝑜𝑛𝑒𝑠 𝑇 𝑥
𝑑𝑖 𝑖
𝑖=1
𝑐𝑜𝑖𝑛𝑐𝑖𝑑𝑎𝑛.
Además de la cota superior indicada en el Lema 8, una
Del teorema anterior concluimos que toda solución óptima de solución óptima x∗ para KP-PD puede emplearse para
KP-CT es es cota superior para KP-DUR. El siguiente definir una solución factible para KP-DUR, al repetir x∗ de
problema tiene la forma de la versión clásica del problema de manera periódica dentro del horizonte de tiempo T,
la mochila (KP): T
𝑛 seleccionando cada objeto i para el cual xi∗ = 1, veces
di
𝑝𝑖
𝑚á𝑥 𝑥𝑖 consecutivas, conforme se indica a continuación: Heurística
𝑑𝑖 Primal KP-PDH
𝑖=1
𝑛
(𝐾𝑃 − 𝑃𝐷)
𝑠. 𝑡 𝑤𝑖 𝑥𝑖 ≤ 𝐶, 1. ∀𝑖 ∈ 1, … , 𝑛 , 𝑠𝑖 𝑥𝑖∗ = 1, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑓𝑖𝑗𝑎𝑟
𝑖=1 𝑇
𝑥𝑖 ∈ 0,1 , ∀𝑖 ∈ {1, … , 𝑛} 𝑇𝑖 ≔ 𝑘𝑑𝑖 + 1 ∶ 0 ≤ 𝑘 <
𝑑𝑖

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
5

𝑇 𝑛 𝑝𝑖
𝑥𝑖𝑡 ≔ 1, ∀𝑡 ∈ 𝑇𝑖 𝑧= 𝑡=1 𝑖=1 𝑑 𝑥𝑖𝑡 el valor de la solución asociada a 𝑋
𝑖
𝑦𝑖𝑡 +𝑑 𝑖 ≔ 1, ∀𝑡 ∈ 𝑇𝑖 /{𝑇 − 𝑑𝑖 + 1} 𝑋 ∈ {0,1}𝑛×𝑇 la matriz con la mejor solución factible
𝑧𝑖𝑡+𝑙 ≔ 1, ∀𝑡 ∈ 𝑇𝑖 , 0 ≤ 𝑙 ≤ 𝑑𝑖 encontrada hastael momento;
𝑝
𝑧 = 𝑇𝑡=1 𝑛𝑖=1 𝑖 𝑥𝑖𝑡 el valor de la mejor solución factible
𝑑 𝑖
2. 𝐹𝑖𝑗𝑎𝑟 𝑥𝑖𝑡 ≔ 𝑦𝑖𝑡 = 𝑧𝑖𝑡 = 0 𝑒𝑛 𝑡𝑜𝑑𝑜𝑠 𝑙𝑜𝑠 𝑑𝑒𝑚á𝑠 𝑐𝑎𝑠𝑜𝑠. encontrada hasta el momento;

Es fácil comprobar que (𝑥 , 𝑦, 𝑧) es una solución factible para L la lista de ternas que representan las decisiones de
KP-DUR. Utilizaremos esta heurística primal dentro del ramificación tomadas
esquema tipo branch-and-bound para la solución de KP-DUR
hasta llegar al nodo actual;
que describimos en adelante.
Q la cola de nodos por procesar, cada uno representado por
su lista de ternas asociada;
2.3 Algoritmo KPD-BB
A ∈ Zn×T la matriz de disponibilidad de objetos para el nodo
actual;
Tenemos todos los componentes necesarios para formular un
esquema tipo branch-and-bound para KP-DUR. 𝐶𝑡 = 𝐶 − 𝑖: 𝐴𝑖𝑡 =1 = 𝑤𝑖 capacidad residual de la mochila en
Emplearemos la heurística KP-PDH para construir una el período t, para el nodo actual. Es importante señalar que
solución factible. los elementos de las matrices solución ˆXit, Xit indican la
presencia o no del objeto i dentro de la mochila en el período
Luego de análisis computacionales preliminares, decidimos t. Es decir, corresponden realmente a las variables zit del
emplear el modelo KP-PD (por sobre el modelo KPCT) para modelo KP-DUR.
el cálculo de cotas superiores durante la exploración del árbol
de branch-and-bound. Esta decisión se tomó al evaluar la Producere: KPD-BB
calidad de las cotas obtenidas frente al tiempo de cálculo input: n, C,T,(p),(w),(d);
necesario sobre varias instancias de prueba. output: z,(X);
begin
Por otra parte, el modelo KP-PD puede ser extendido de 1. [inicializar]
manera natural para incorporar restricciones adicionales que
z : = 0;
aparecen a partir de las decisiones de ramificación, como
veremos más adelante. Las decisiones de ramificación 𝑧 : = 0;
(branching) consisten en forzar o prohibir que un objeto i 𝑋:=0
ingrese a la mochila en un período t. Representaremos estas 𝑋:=0
decisiones mediante ternas de la forma (i, t, k) donde: 𝐶𝑡 : = 𝐶, ∀𝑡 {1, … , 𝑇}

1, 𝑠𝑖 𝑒𝑙 𝑜𝑏𝑗𝑒𝑡𝑜 𝑖 𝑖𝑛𝑔𝑟𝑒𝑠𝑎 𝑒𝑛 𝑙𝑎 𝑚𝑜𝑐𝑕𝑖𝑙𝑎 𝑒𝑛 𝑒𝑙 2. [calcular una solución factible empleando la

𝑘= 𝑝𝑒𝑟í𝑜𝑑𝑜 𝑡; huerística primal]
0, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 encontrar una solución óptima 𝑥 de la instancia
asociada KP-PD
Cada nodo del árbol de búsqueda tiene asociada una lista de 𝑛 𝑇
ternas que representan las decisiones tomadas previamente. 𝑇 𝑥𝑖 𝑠𝑖 𝑡 ≤ 𝑑𝑖
Al iniciar el procesamiento del nodo, la información de esta 𝑧 ∶= 𝑇 𝑝 𝑖 𝑥𝑖 , 𝑋𝑖𝑡 ≔ 𝑑𝑖
𝑑𝑖
lista se emplea para calcular, para cada período t ∈ {1, ..., T}, 𝑖=1 0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
el conjunto de objetos At que pueden ser seleccionados para
ingresar en la mochila (a los que llamamos objetos 3. [incluir en L algunas decisiones de ramificaciones
disponibles), además de la capacidad residual de la misma forzadas por el modelo]
𝐶𝑡 . Se emplea luego una versión modificada del algoritmo de agregar a L las ternas (i,t,0), ∀i ∈ {1, … , n},
Horowitz-Sahni [7] para calcular una cota superior: se ∀t ∈ T − di + 2, … , T forzadas por (10);
resuelven modelos KP-PD para T problemas clásicos de la 4. Q : = {L};
mochila, cada uno sobre el conjunto At de objetos, y 5. [lazo principal del esquema branch-and-bound]
considerando una mochila con capacidad 𝐶𝑡 para t ∈ {1, ..., while 𝑄 ≠ ∅ do
T}. La suma de los valores óptimos sobre todos los períodos retirar la primera lista L de Q;
es una cota superior al valor óptimo de KP-DUR para el nodo
actual. El algoritmo completo está descrito a continuación. 6. [inicio del procesamiento de un nodo]
Sean: obtener la matriz de disponibilidades A y las
capacidades resicuales 𝐶𝑡 a partir de las ternas de L;
𝑋 ∈ {0,1}𝑛×𝑇 la matriz solución para el nodo actual;
7. [calcular la cota superior KP-PD]

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
6

for t := 1 to T do
begin El objeto i está disponible en el período t si Ait ∈ {−1,−2}.
 encontrar una solución óptima 𝑥 𝑡 de KP-PD
con los objetos disponibles en cada El cambio de era protagonizado por el advenimiento de la
columna At de A, empleando la apacidad Televisión Digital, evidencia las profundas
residual 𝐶𝑡 transformacionesque esta nueva tecnología incorpora a
 almacenar 𝑥 𝑡 en la columna t de la matriz laexperiencia del usuario, ya que además de entretenersecon
solución para el nodo actual: los contenidos que se difunden por las estacionesde
𝑋𝑖𝑡 ≔ 1, 𝑠𝑖 𝐴𝑖𝑡 = 1 ó 𝑥𝑖𝑡 = 1 televisión, éste tiene la posibilidad de interactuarcon este
0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 medio de comunicación a través de diferentesaplicaciones y
end; modalidades, revolucionando así, elmodelo tradicional de
end for; mirar televisión. Actualmente,los estándares de transmisión
𝑇 𝑛 de TV Digital adoptadosa nivel mundial permiten el
𝑝𝑖
𝑧 ∶= 𝑋 transporte ágil de grandesvolúmenes de información, lo que
𝑑𝑖 𝑖𝑡
𝑡=1 𝑖=1 propicia la disponibilidadde excesiva oferta televisiva en los
8. [podado del árbol de búsqueda] [Link] sobreoferta de alternativas de entretenimiento
if 𝑧 ≤ z end while; originará un escenario en el que el usuario se enfrentea una
amplísima cantidad de programación disponible,que a pesar
9. [comprobar si la solución actual es factible] de contar
if 𝑋es factible para KP-DUR
begin A partir de esta matriz, se construyen T instancias de
[actualizar la mejor solución obtenida hasta KPPD,cada una de las cuales emplea los objetos
el momento] disponiblesen un período determinado. La capacidad de la
z := 𝑧 ; mochilaen cada instancia corresponde a la capacidad residual
𝑋𝑖𝑡 := ˆ𝑋𝑖𝑡 , ∀ i ∈ {1, ..., n}, ∀ t ∈ {1, ..., parael período correspondiente, luego de descontar el pesode
T}; los objetos presentes (Ait = 1):
end;
end while; 𝐶𝑡 ≔ 𝐶 − 𝑤𝑖
else 𝑖:𝐴𝑖𝑡 =1
begin
[ramificación] Cada instancia de KP-PD se resuelve hasta la optimalidad
generar dos ternas nuevas t1 := (i, t, 1), t2 := empleando una versión modificada del algoritmo
(i, t, 0); deHorowitz-Sahni. La matriz 𝑋∈ 0, 1 𝑛 𝑥 𝑇 se
L1 := L ∪ {t1}, L2 := L ∪ {t2}; construyeusando como columnas las soluciónes óptimas de
agregar las dos nuevas listas L1, L2 al inicio las Tinstancias de KP-PD, además de la información de
de la cola Q; objetospresentes o prohibidos. Si el valor de la función
end; objetivopara 𝑋 es inferior al valor de la mejor solución
end while; factibleencontrada hasta el momento, la solución es
end. desechada(poda del árbol).

El primer paso en el procesamiento de un nodo del árbol de Caso contrario, se verifica la factibilidad de 𝑋 Si esta
búsqueda consiste en recuperar la lista asociada de ternas de solución es factible, se actualiza la mejor solución X:= 𝑋,z:=
ramificación y construir a partir de ésta una matriz de 𝑧. Si 𝑋 no es factible, una ramificación tiene lugar ydos
disponibilidades A ∈ {−1,−2, 0, 1}n×T que identifica para cada nuevas listas son agregadas a la cola 𝑄. Para la
objeto i en cada período t uno de cuatro posibles estados: ramificaciónhemos investigado tres posibles técnicas:
 libre (Ait = −1), si el objeto puede ser seleccionado
para ingresar en la mochila;  La primera técnica de ramificación busca en las
 posible (Ait = −2), si el objeto no puede ingresar en matricesA y en la solución actual 𝑋 el primer
la mochila en el período actual, pero puede estar elementolibre que haya sido seleccionado por la cota
presente en la misma debido a que podría ingresar superior:
en un período anterior;
for i := 1, ..., n do
 presente (Ait = 1), si el objeto forzosamente está
for t := T, ..., 1 do
presente en la mochila en el período actual, por
alguna decisión de ramificación tomada previamente if 𝐴 𝑖𝑡 = −1 and𝑋𝑖𝑡 = 1, then
durante la exploración del árbol de búsqueda;
𝑡1 ∶= 𝑖, 𝑡, 1 ,
 prohibido (Ait = 0), si el objeto no puede estar en la 𝑡2 ∶= 𝑖, 𝑡, 0 .
mochila en el período actual.

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
7

break; segundo objeto en el tiempo t = 1. El valor de esta solución

inicial es z = 2 + 2 +11 = 15. Se generan entonces las ternas
 La segunda técnica de ramificación busca forzadas por el modelo y se construye la lista inicial.
simplemente el primer objeto libre:
𝐿 ∶= 1,4,0 , 2,3,0 , 2,4,0 , 3,4,0 , 4,3,0 , 4,4,0 .
for i := 1, ..., n do
for t := T, ..., 1 do Luego entramos en el lazo principal del esquema branch
if 𝐴 𝑖𝑡 = −1, then andbound.A partir de L se construye la primera matriz de
disponibilidades:
𝑡1 ∶= 𝑖, 𝑡, 1 ,
𝑡2 ∶= 𝑖, 𝑡, 0 . -1 -1 -1 -2
break; -1 -1 -2 -2
𝐴= -1 -1 -1 -2
La tercera técnica de ramificación ordena las filas de las -1 -1 -2 -2
matrices A y 𝑋 en sentido descendente de los valoresde los
objetos, siendo i = 1 la fila que correspondeal objeto de
mayor valor e i = n la fila asociadaal de menor valor Con la matriz A se construyen T instancias de KP-PD
(originalmente, las filas están ordenadas descendentemente independientes, cada una con los objetos disponibles y la
por la densidad p/wd de los objetos). Luego se procede como capacidad residual existente en cada período de tiempo. En
en la primera técnica. este caso, para as 4 instancias todos los objetos están
disponibles y la capacidad residual es la capacidad total de la
En los tres casos, el elemento (i, t) seleccionado es empleado mochila. Al resolver cada instancia empleando nuestra
para construir dos ternas t1, t2 que representan las decisiones modificación del algoritmo de Horowitz-Sahni, la solución
de forzar la entrada del objeto i en la mochila en el período t, encontrada es:
o de prohibir su ingreso. Con estas ternas, se definen las
nuevas listas L1:= L ∪ {t1} yL2:= L ∪ {t2}, las mismas que 1 1 1 1
se añaden a la cola Q de listas por procesar, y la iteración 1 1 1 1
termina. El algoritmo termina cuando todas las listas de 𝑋=
0 0 0 0
ternas pendientes en Q han sido procesadas, y devuelve como
resultado el valor óptimo del problema. 0 0 0 0

Ejemplo 1. Veamos el funcionamiento general del esquema con un valor de ˆz = 18, que es mayor que el valor de la
para la siguiente instancia de KP-DUR: mejor solución z. Se comprueba entonces si esta solución es
Se tiene una mochila con capacidad C = 5, y 4 objetos con las factible o no, en nuestro caso es infactible. Se procede a crear
siguientes características: dos ternas de ramificación, empleando para este ejemplo la
primera técnica de ramificación, que selecciona i = 1, t = 3 y
t1:= (1, 3, 1), t2:= (1, 3, 0). Con estas ternas se crean las
𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑝𝑖 ∶ 2 11 6 3 nuevas listas L1 = L ∪ {t1}, L2 = L ∪ {t2} y se las agrega al
inicio de la cola Q, con lo que termina la primera iteración
𝑝𝑒𝑠𝑜𝑠 𝑤𝑖 ∶ 1 4 4 2 del lazo principal. En la segunda iteración, se retira la
primera listaL1 de la cola, la matriz de disponibilidades
2 3 2 3
𝑑𝑢𝑟𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑑𝑖 ∶ obtenida a partir de ésta es:

Se quiere maximizar el valor total almacenado en la mochila 1 1 1 1

en un horizonte temporal T = 4, y los objetos están ordenados 1 1 1 0
de acuerdo a sus densidades
𝑝1
>
𝑝2
>...>
𝑝4
. Laprimera 𝐴= 0 0 0 0
𝑤1𝑑1 𝑤2𝑑2 𝑤4𝑑4
solución obtenida mediante la heurística primal vienedada 0 0 0 0
por:
-1 -2 1 1 Para esta nueva matriz de disponibilidades se crean las T
-1 -1 -2 -2 instancias de KP-PD y se resuelve independientemente cada
𝑋= -1 -1 -1 -2 una de ellas. Las instancias para t ∈ {1, 2} tienen nuevamente
-1 -1 -2 -2 los cuatro objetos y toda la capacidad de la mochila
disponibles. Para t ∈ {3, 4}, están disponibles los objetos 2,
3,4 y la capacidad residual es 𝐶𝑡 = C − w1 = 4. Aun así, el
donde Xit tiene el valor de 1 cuando el objeto i ∈ {1, ..., 4}
resultado obtenidosigue siendo el mismo:
está presente en la mochila en el período t ∈ {1, ..., 4}. En
este caso, la solución consiste en ingresar a la mochila el
primer objeto en los tiempos t = 1 y t = 3, e ingresar el

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
8

1 1 1 1 2. Débilmente correlacionadas, en las cuales C = 3R, T

1 1 1 1 =⌈1.1R⌉, y los valores, pesos y duraciones son
𝑋= 0 0 0 0 generados como se indica a continuación:
0 0 0 0
𝑝𝑗 ↝ 𝑈 1,𝑅 , ∀𝑗 ∈ 1, … , 𝑛 ,
𝑤 𝑗 ↝ 𝑈 𝑝 −𝑅 , 𝑝 +𝑅 , ∀𝑗 ∈ 1, … , 𝑛 ,
𝑗 𝑗
Nuevamente, tenemos que el valor 𝑧 es mayor que el de la 10 10

solución actual z. Además, la solución es infactible y 𝑑𝑗 ↝ 𝑈 𝑝 𝑅 𝑅 , ∀𝑗 ∈ 1, … , 𝑛 .

𝑗 −10 , 𝑝 𝑗 +10
volvemos a generar dos nuevas ternas de ramificación t3:=
(1, 1, 1), t4:=(1, 1, 0), junto con las nuevas listas L3 = L1 3. Fuertemente correlacionadas, en las cuales C = 3R,
∪{t3}, L4 =L1 ∪ {t4}, que son agregadas a la cola Q. Siete T =⌈2.1R⌉, y los valores, pesos y duraciones se
iteraciones más adelante, se llega a la solución factible: generan por medio de:

1 1 1 1 𝑝𝑗 ↝ 𝑈 1,𝑅 , ∀𝑗 ∈ 1, … , 𝑛 ,
0 0 0 0 𝑤 𝑗 ↝ 𝑈 𝑝 +𝑅 , , ∀𝑗 ∈ 1, … , 𝑛 ,
𝑋= 𝑗 10
1 1 1 1 𝑑 𝑗 ↝ 𝑈 2𝑝 𝑅 , ∀𝑗 ∈ 1, … , 𝑛 .
𝑗 +10
0 0 0 0
Con este generador se construyeron 27 instancias de prueba
con un valor de ˆz = 16. Como este valor supera al de la para KP-DUR, las cuales se detallan en la Tabla1.
mejor solución encontrada hasta el momento, se actualiza
ésta última: R
n Tipo 10 20 50
1 1 1 1 1 Instancia_1 Instancia_4 Instancia_7
0 0 0 0 20 2 Instancia_2 Instancia_5 Instancia_8
𝑋= 1 1 1 1 3 Instancia_3 Instancia_6 Instancia_9
0 0 0 0 1 Instancia_10 Instancia_13 Instancia_16
50
2 Instancia_11 Instancia_14 Instancia_17
Instancias

Luego de 11 iteraciones, termina la exploración de todas las 3 Instancia_12 Instancia_15 Instancia_18

listas pendientes en Q, y se constata que esta solución es la 1 Instancia_19 Instancia_22 Instancia_25
solución óptima de la instancia. 100
2 Instancia_20 Instancia_23 Instancia_26
3 Instancia_21 Instancia_24 Instancia_27
3. RESULTADOS COMPUTACIONALES

3.1 Instancias de Prueba

Tabla 1. Instancias de prueba para KP-DUR.
Para analizar el desempeño práctico del algoritmo, se
utilizaron instancias construidas mediante la modificación de
un algoritmo de generación de instancias para la versión 3.2 Eficiencia computacional
clásica de KP elaborado por David Pisinger [15]. Se
realizaron cambios al mismo para que construya instancias El desempeño computacional de nuestro algoritmo KPDBB
para KP-DUR agregando duraciones a los objetos y un fue comparado sobre las instancias de prueba descritas
horizonte temporal T. El algoritmo de generación utilizados anteriormente contra el desempeño de una implementación
parámetros: un entero n que indica el número de objetos y un directa del modelo KP-DUR en el solver general para
entero R en función del cual se definen todas las demás programas enteros SCIP, versión 2.1 [1]. Las pruebas
variables del problema. Este algoritmo genera tres tipos de computacionales se desarrollaron en una máquina con
instancias: procesador AMD Athlon (tm) X2 Dual-Core QL-64 2.10
GHz con memoria RAM de 4.00 GB y un sistema operativo
1. No correlacionadas, en las cuales C = 3R, T = R, y Windows 7 de 64 bits. El código fue compilado empleando el
los valores, pesos y duraciones son generados compilador GNU GCC versión [Link] a
independientemente simulando distribuciones continuación en más detalle algunas instancias relevantes. Un
uniformes de probabilidad: factor a considerar al analizar la calidad de una solución es la
brecha de optimalidad (gap):
𝑝𝑗 ↝ 𝑈 1,𝑅 , ∀𝑗 ∈ 1, … , 𝑛 ,
𝑤 𝑗 ↝ 𝑈 1,𝑅 , ∀𝑗 ∈ 1, … , 𝑛 , 𝑐𝑜𝑡𝑎 𝑠𝑢𝑝𝑒𝑟𝑖𝑜𝑟 − 𝑚𝑒𝑗𝑜𝑟 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑎𝑙𝑐𝑎𝑛𝑧𝑎𝑑𝑎
𝑔𝑎𝑝 =
𝑑 𝑗 ↝ 𝑈 1,𝑅 , ∀𝑗 ∈ 1, … , 𝑛 . 𝑚𝑒𝑗𝑜𝑟 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑎𝑙𝑐𝑎𝑛𝑧𝑎𝑑𝑎

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
9

Reportamos aquí únicamente resultados obtenidos con KPD-

BB configurado para usar la primera heurística de
ramificación, pues para ésta se presentó el mejor
comportamiento en todas las instancias. Resultados más
detallados se describen en [16]. El comportamiento de los
algoritmos para la instancia 14 está detallado en la Figura1.
Esta instancia es del tipo débilmente correlacionada, con n =
50 y R = 20. Podemos notar que el valor dela cota superior
KP-PD es de 596, encontrada en t = 0sy es muy cercano al
valor de la cota obtenida por SCIP, cuyo valor es de 589 en t
= 1s. La primera solución factible encontrada mediante la
heurística primal tuvo un valor de 566 obtenida en el tiempo t
= 0s mientras que la primera solución factible encontrada por
SCIP en el tiempo t = 10s tiene un valor de 580. Dentro del
período de 1 hora KPD-BB encontró una solución factible
con un valor de 579, que es un 1% menor al valor 585 dela Figura 2. Comportamiento de los algoritmos para la instancia 15, heurística
solución óptima encontrada por SCIP en t = 260s. El gap de ramificación 1.
inicial de KPD-BB fue de 5%, y se redujo a 2% en un
período de una hora. Sin embargo, el esquema tiene problemas para “cubrir el
último tramo” de la brecha de optimalidad (por lo general,
menor al 5%). Esto puede deberse a la simetría de las
soluciones factibles, la misma que fuerza a KPD-BB a
desperdiciar tiempo de cálculo explorando soluciones de
igual valor. Esto ocurre sobre todo en las instancias del tipo
fuertemente correlacionadas. El gap inicial de KPD-BB fue
de 7%, y se redujo a 6% en un período de una hora. En la
Figura 3 se presentan los resultados para instancia 27, que es
del tipo fuertemente correlacionada con n = 100 y R = 50. El
valor de la cota superior KP-PD encontrada en t = 0s es de
1491, que es menor al de la última cota obtenida por SCIP,
cuyo valor es de 1493 ent = 1411s. La primera cota superior
obtenida por SCIP tuvo un valor de 1504 en t = 135s.

La primera solución factible encontrada mediante la

heurística primal tiene un valor de 1400 obtenida en el
Figura 1. Comportamiento de los algoritmos para la instancia 14, heurística tiempo t = 1s mientras que la primera solución factible
de ramificación 1. encontrada por SCIP tiene un valor de 1400 en el tiempo t =
1411s. KPD-BB encontró una solución factible de mejor
En la Figura 2 se reportan los resultados obtenidos por los valor 1406 en t = 47s y ésta no pudo ser mejorada dentro del
algoritmos SCIP y KPD-BB para la instancia 15. Esta tiempo de cálculo permitido. SCIP encontró una solución
instancia es del tipo fuertemente correlacionada con n = 50 y factible más durante todo el tiempo de cálculo permitido
R = 20. Podemos observar que el valor de la cota superior cuyo valor es de 1416, obtenida en t = 2627s. El gap inicial
KP-PD fue de 422 encontrada en t = 0s que es un 2% mayor a de KPD-BB fue de 6,5%, y se redujo a 6% en un período de
la obtenida por SCIP, con un valor de408 en t = 6s. La una hora. Se corrobora nuevamente que para instancias de
primera solución factible encontrada mediante la heurística gran tamaño, KPD-BB encuentra de forma eficiente
primal tuvo un valor de 391obtenida en el tiempo t = 0s soluciones factibles y cotas superiores de valores similares a
mientras que la primera solución factible encontrada por aquellas obtenidas por SCIP en untiempo de cálculo
SCIP en el tiempo t = 8sEsta solución es un 1% menor que la considerablemente menor.
solución óptima encontrada por el SCIP en t = 20s, de valor
403, que fue verificada como óptima en t = 1124s. Puede
notarse que los primeros resultados obtenidos mediante la
heurística prima y la cota superior de KPD-BB son
competitivos con aquellos obtenidos por SCIP, tomando en
cuenta su valor y su tiempo de cálculo tuvo un valor de 391.
KPD-BB encontró una solución factible con un valor de 395
en el tiempo t = 23s la misma que no pudo ser mejorada en
todo el período de cálculo.

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
10

[3] M. Bartlett, A. Frisch, Y. Hamadi, [Link], S. Tarim,and

C. Unsworth. The temporal knapsack problemand its
solution. In R. Barták and M. Milano,
editors,Integration of AI and OR Techniques in
Constraint Programming for Combinatorial
Optimization Problems, volume 3524 of Lecture Notes
in Computer Science, pages34–48. Springer Berlin /
Heidelberg, 2005.

[4] G. Dantzig. Discrete variable extremum problems. Math.

Oper. Res., 5(2):266–277, Apr. 1957.

[5] M. R. Garey and D. S. Johnson. Computers and

Intractability:A Guide to the Theory of NP-
Completeness. W.H. Freeman & Co., New York, NY,
Figura 3. Comportamiento de los algoritmos para la instancia27, heurística USA, 1979.
de ramificación 1.
[6] P. Gilmore and R. Gomory. A linear
La simetría de soluciones sigue demostrando ser un problema
programmingapproach to the cutting stock problem.
para el esquema planteado ya que no permite explorar el
Math. [Link]., 9(6):849–859,Nov. 1961.
árbol de decisiones de manera más eficiente.
[7] E. Horowitz and S. Sahni. Computing partitionswith
4. CONCLUSIONES
applications to the knapsack problem. J. ACM,21:277–
292, April 1974.
Hemos presentado un modelo de programación entera para
una versión dinámica del problema de la mochila, en la cual
[8] R. M. Karp. Reducibility among combinatorial problems.
los objetos tienen asociados tiempos de permanencia en la
In R. E. Miller and J. W. Thatcher, editors, Complexity
mochila y se busca maximizar el valor en la misma dentro de
of Computer Computations, The IBM
un horizonte de tiempo. Hemos propuesto un algoritmo de
ResearchSymposia Series, pages 85–103.
solución exacta para este problema de optimización
PlenumPress,New York, 1972.
combinatoria, basado en el esquema de branch-and-bound.
Finalmente, hemos estudiado el rendimiento computacional
[9] H. Kellerer and U. Pferschy. A new fully polynomialtime
de nuestro algoritmo KPDBBal comparar su desempeño
approximation scheme for the knapsackproblem. J.
sobre instancias de prueba contra el desempeño del solver
Comb. Optim., 3(1):59–71, 1999.
lineal entero general SCIP. Los experimentos
computacionales de la sección precendente permiten concluir
[10] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack
que el esquema KPD-BB encuentra rápidamente cotas
Problems. Springer, Germany, 2004.
superiores y soluciones primales de un valor aceptable, pero
que generalmente no consigue cerrar la brecha de
[11] S. Martello and P. Toth. An upper bound for thezero-one
optimalidad dentro de un tiempo de cálculo razonable. Por el
knapsack problemand a branch and bound algorithm.
contrario, SCIP es más eficiente reduciendo la brecha de
European Journal of Operational Research,1(3):169–
optimalidad pero requiere de un mayor tiempo de cálculo
175,May 1977.
para encontrar la primera solución factible, sobre todo en
instancias grandes (por ejemplo, en las instancias 22 a la 27).
[12] S. Martello and P. Toth. Knapsack Problems:
De esta manera, nuestro esquema de solución KPD-BB es
Algorithms and Computer Implementations. Wiley,
particularmente adecuado para situaciones donde el tiempo
NewYork, NY, USA, 1990.
de cálculos es un factor crítico a considerar. Por ejemplo,
para aplicaciones en tiempo real.
[13] J. D. Papastavrou, S. Rajagopalan, and A. J. Kleywegt.
The dynamic and stochastic knapsack problem with
REFERENCIAS
deadlines. Management Science, 42:1706–1718,
December 1996.
[1] T. Achterberg. Scip: Solving constraint integer programs.
Mathematical Programming Computation, 1(1):1–41,
[14] R. Parra-Hernandez, D. Vanderster, and N. J.
[Link]://[Link]/[Link]/MPC/artile/view/4.
Dimopoulos. Resource management and knapsack
formulations on the grid. In Proceedings of the
[2] E. Balas and E. Zemel. An algorithm for large
5thIEEE/ACM International Workshop on Grid
zerooneknapsack problems. [Link]. Res.,
Computing, GRID ’04, pages 94–101,Washington, DC,
28(5):1130–1154, 1980.
USA,2004. IEEE Computer Society.

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014

ACERCA DE UNA VERSIÓN DINÁMICA DEL PROBLEMA DE LA MOCHILA
11

[15] D. Pisinger. David pisinger’s optimization codes.

[Link] [Link].

[16] B. Silva. Algoritmos de solución para una versión

dinámica del problema de la mochila. Tesis de grado en
Ingeniería Matemática, Escuela Politécnica Nacional,
Quito, Ecuador, 2014.

[17] V. V. Vazirani. Approximation algorithms. Springer,

Berlin, 2001.

REVISTA EPN, VOL. 34, NO. 1, NOVIEMBRE 2014