Problema de la mochila

Modelos y Optimizaci´on I Redactado por Tom´as Bruno Facultad de Ingenier´ıa de la Universidad de Buenos Aires Versi´on 1.0 - Octubre 2013

´Indice 1. Formulaci´ on Lineal

3

2. Aproximaciones 4 2.1. Aproximaci´on a trav´es de coeficiente de rendimiento. . . . . . 4 2.2. Evaluaci´on de la heur´ıstica . . . . . . . . . . . . . . . . . . . . 4 2.3. Mejoramiento a trav´es de la comparaci´on con el elemento cr´ıtico. 6 3. An´ alisis de cotas. 3.1. Relajaci´on lineal. . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Dantzig. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Martello & Toth . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Variantes

8 8 8 9 12

5. Aplicaciones 14 5.1. Merkle-Hellman: . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2. Otras aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . 14

1

Introducci´ on El problema de la mochila es un problema simple de entender: hay una persona que tiene una mochila con una cierta capacidad y tiene que elegir que elementos pondr´a en ella. Cada uno de los elementos tiene un peso y aporta un beneficio. El objetivo de la persona es elegir los elementos que le permitan maximizar el beneficio sin excederse de la capacidad permitida. A la vez es un problema complejo, si por complejidad nos referimos a la computacional. “Un problema se cataloga como inherentemente dif´ıcil si su soluci´on requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado.”[5] El problema de la mochila forma parte de una lista hist´orica de problemas N P − Completos elaborada por Richard Karp en 1972[4]. En el caso del problema de la mochila, si cont´aramos con 4 productos, para saber cual es la mejor soluci´on podr´ıamos probar las 24 = 16 posibilidades. El 2 se desprende del hecho de que cada decisi´on es incluir o no al producto y el 4 de la cantidad de productos. 16 posibilidades es un n´ umero manejable, sin embargo, si la cantidad de elementos por ejemplo ascendiera a 20, tendr´ıamos que analizar nada m´as y nada menos que 220 = 1,048,576 posibilidades El siguiente apunte tiene como objetivo proveer una introducci´on al problema de la mochila. En la primera secci´on se analizar´a como obtener una soluci´on o´ptima para el problema utilizando la t´ecnica programaci´on lineal. Luego, en la segunda secci´on, se analizar´an alternativas que permiten obtener soluciones aproximadas a trav´es del uso de heur´ısticas. Para medir el desempe˜ no de las heur´ısticas, se tiende a utilizar cotas. Algunas de estas cotas ser´an analizadas en la tercera secci´on. En la cuarta secci´on se describen algunas de las variantes al problema de la mochila est´andar. Por u ´ltimo, en la quinta secci´on se presentar´an aplicaciones del problema de la mochila.

2

1.

Formulaci´ on Lineal

Una de las t´ecnicas matem´aticas que se puede utilizar para la resoluci´on de este problema es la programaci´on lineal. Definiendo a c como la capacidad de la mochila pi como el beneficio unitario obtenido por ingresar el producto i en la mochila wi como el peso del producto i n como la cantidad de productos c, pi y wi como valores enteros y positivos se puede plantear el modelo como: n X

w i xi ≤ c

(Capacidad)

i=1

max →z =

n X

p i xi

(Funcional)

i=1

No obstante, el problema que tiene esta t´ecnica es que no siempre se puede resolver debido a su complejidad matem´atica. En esas ocasiones, es necesario recurrir a heur´ısticas. Una heur´ıstica es un procedimiento que en la mayor´ıa de las ocasiones nos permite obtener una buena soluci´on pero que no necesariamente es la o´ptima.

3

2. 2.1.

Aproximaciones Aproximaci´ on a trav´ es de coeficiente de rendimiento.

Una soluci´on intuitiva pero que puede no ser o´ptima podr´ıa elaborarse ordenando los productos en forma descendente seg´ un la proporci´on ri =

pi wi

y metiendo elementos de esta lista ordenada hasta que no se pueda ingresar el siguiente elemento a la mochila. Desde este punto en adelante, siempre se asumir´a que los elementos del conjunto se encuentran ordenados seg´ un esta proporci´on. Ejemplo 1. Considerando la siguiente instancia del problema de la mochila con capacidad c = 65 N A B C D E

p 100 80 30 15 10

w 20 20 30 20 100

r 5 4 1 0.75 0.1

Aplicando la heur´ıstica mencionada, elegir´ıamos los productos A y B ya que al tratar de ingresar el producto C estar´ıamos excediendo la capacidad permitida. El resultado obtenido entonces ser´ıa Z 0 = 100 + 80 = 180 Es importante notar que los elementos en la tabla est´an ordenados seg´ un la proporci´on ri . Si no estuvieran ordenados, el primer paso consistir´ıa en ordenarlos.

2.2.

Evaluaci´ on de la heur´ıstica

Pese a que la heur´ıstica propuesta en el punto anterior tiende a funcionar adecuadamente en la mayor´ıa de los casos, existen casos patol´ogicos que pueden tener como consecuencia un rendimiento desastroso. Definiendo a 4

z como el valor de la soluci´on o´ptima z 0 como el valor de la soluci´on obtenido aplicando la heur´ıstica definida en la secci´on 2.1 z0 z

como ´ındice de performance de la heur´ıstica. Se puede observar que si la heur´ıstica obtuviera la soluci´on o´ptima, el rendimiento para esa instancia ser´ıa 1. se puede observar que pueden existir casos en el cual el ´ındice de performance de la heur´ısitica sea tan cercano a 0 como se quiera. Demostraci´ on. Considerando la siguiente instancia del problema de la mochila con capacidad c = k (con k > 1) N A B

p 1+δ k

w 1 k

r 1+δ 1

Aplicando el algoritmo de la secci´on 2.1, elegir´ıamos al producto A y en consecuencia nuestro funcional ser´ıa igual a 1. En cambio, el valor de la soluci´on o´ptima ser´ıa k. En este caso, el ´ındice de performance de la heur´ıstica en consecuencia ser´ıa: cal =

1+δ k

Para valores elevados de k: l´ım cal =

k→∞

1+δ =0 k

Ejemplo 2. Considerando la siguiente instancia del problema de la mochila con capacidad c = 100, N A B

p 2 100

w 1 100

r 2 1

Se puede observar que la soluci´on o´ptima estar´ıa dada por la selecci´on del elemento B, en consecuencia z = 100. En cambio, utilizando la heur´ıstica descripta, el valor obtenido es z 0 = 2. El ´ındice de performance de la heur´ıstica en este caso particular resulta: cal = 5

2 100

2.3.

Mejoramiento a trav´ es de la comparaci´ on con el elemento cr´ıtico.

Se puede realizar una peque˜ na modificaci´on al algoritmo para asegurar que el ´ındice de calidad de la heur´ıstica en ning´ un caso sea tan peque˜ no. En primer lugar es necesario definir al elemento cr´ıtico s. El elemento cr´ıtico es el primer elemento que, en caso de incluirlo, se excede la capacidad permitida. La heur´ıstica se puede mejorar agregando un paso posterior que consiste en comparar al resultado obtenido con el beneficio del elemento cr´ıtico, ps . Es decir, en definitiva, el resultado obtenido ser´ıa: 00

z = max(

s−1 X

pi ; p s )

i=1

Esto permitir´ıa que por ejemplo en el caso descripto en el ejemplo 2, el valor obtenido aplicando esta heur´ıstica mejorado sea de k y en consecuencia, iguale la soluci´on ´optima. Peor ´ındice de performance de la heur´ıstica mejorada Considerando la siguiente instancia del problema de la mochila con capacidad c = 2k (con k > 1) N A B C

p 1+δ k k

w 1 k k

r 1+δ 1 1

Aplicando el algoritmo mejorado, elegir´ıamos a los productos A y B obteniendo un valor de funcional z 00 = 1 + δ + k en comparaci´on a z = 2k En consecuencia el peor ´ındice de performance ser´ıa igual a: z 00 1 = k→∞ z 2 l´ım

Ejemplo 3. Considerando la siguiente instancia del problema de la mochila con capacidad c = 200, N A B C

p 2 100 100

w 1 100 100

6

r 2 1 1

Se puede observar que la soluci´on o´ptima estar´ıa dada por la selecci´on de los elementos B y C, en consecuencia z = 200. En cambio, utilizando la heur´ıstica descripta, el valor obtenido es z 0 = 102. El ´ındice de performance de la heur´ıstica en este caso particular resulta: cal =

7

102 200

3.

An´ alisis de cotas.

En la secci´on 1 se estableci´o que no siempre es posible calcular la soluci´on o´ptima de una instancia del problema de la mochila debido a la complejidad computacional. En consecuencia, en la secci´on 2 se busc´o una alternativa a trav´es del planteo de heur´ısticas. No obstante, todav´ıa no se estableci´o como determinar si una heur´ıstica es buena o no. Para determinar el desempe˜ no de una heur´ıstica en una instancia en particular, resulta u ´til poder acotar el problema. Si se supiera cual es el m´aximo valor que podr´ıa valer la soluci´on ´optima, se contar´ıa con m´as informaci´on para saber si es buena la soluci´on que se obtuvo con la heur´ıstica. A continuaci´on se analizar´a una serie de cotas superiores desarrolladas para el problema de la mochila. Se debe tener en cuenta que siempre la soluci´on o´ptima, z, es menor o igual que una cota superior, U . Una cota es superior a otra si se encuentra m´as cerca de la soluci´on ´optima.

3.1.

Relajaci´ on lineal.

Una primera cota que se puede obtener es realizando una corrida definiendo como variables continuas a las variables de decisi´on, xi , . Definiendo a c como la capacidad restante luego de ingresar los elementos que se encuentran en el intervalo [0;s-1] a la mochila, es decir c=c−

s−1 X

wi

i=1

El resultado que se obtendr´ıa en la corrida utilizando variables continuas ser´ıa: U0 = CP (KP ) =

s−1 X i=1

pi + c

ps ws

El primer t´ermino corresponde a la selecci´on de todos los t´erminos con mejor rendimiento que el elemento cr´ıtico s. El segundo t´ermino representa la aplicaci´on del rendimiento del elemento cr´ıtico a la capacidad restante. Es decir, como no se puede ingresar todo el elemento cr´ıtico plantea la idea de fraccionarlo e ingresar todo lo que pueda del producto.

3.2.

Dantzig.

A la soluci´on ´optima considerando a las variables de decisi´on como continuas, Dantzig aplico una condici´on de integralidad. Denominando al operador 8

bac como el operador piso, es decir, que devuelve el mayor entero no es superior que a, obtenemos $ s−1 %   X ps U1 = bCP (KP )c = pi + c ws i=1 Considerando la integralidad de pi y de xi , se obtiene la cota de Dantzig: U1 =

s−1 X i=1

3.3.



ps pi + c ws



Martello & Toth

Martello & Toth superaron la cota de Dantzig estableciendo la integridad del elemento cr´ıtico. Es decir, pidiendo que el elemento cr´ıtico sea ingresado o no, pero dejando de aplicar la capacidad remanente al rendimiento asociado al elemento cr´ıtico. La primera parte del an´alisis consiste en ver cu´al es el mayor resultado posible considerando que no se ingresa el elemento cr´ıtico en la mochila. Al no ingresarlo, existe la posibilidad de que se pueda ingresar un elemento posterior; uno con peor rendimiento pero que permita no exceder la capacidad disponible. En consecuencia, W0 =

s−1 X i=1



ps+1 pi + c ws+1



Notar que ahora el rendimiento al que se aplica la capacidad restante no es el rendimiento del elemento cr´ıtico sino el del elemento siguiente. La segunda parte del an´alisis consiste en ver cu´al es el mayor resultado posible considerando que ahora s´ı se ingresa el elemento cr´ıtico en la mochila. Como justamente por definici´on del elemento cr´ıtico, no se lo pod´ıa ingresar a la mochila si se hab´ıan metido los elementos en el intervalo [0;s-1], la u ´nica posibilidad de ingresar al elemento cr´ıtico es sacando a uno de los elementos en este intervalo. W1 =

s−1 X i=1



ps−1 pi + ps − (ws − c) ws−1



La cota final se desprende de considerar ambos casos y ver cual tiene el mayor valor. U2 = max(W1 ; W2 ) 9

Se puede demostrar que la cota de Martello & Toth es mejor a la planteada por Dantzig [1]. En consecuencia: U2 ≤ U1 Ejemplo. Calculo de cotas para el ejemplo 1. Capacidad: c=65 N A B C D E

p 100 80 30 15 10

w 20 20 30 20 100

r 5 4 1 0.75 0.1

Relajaci´ on lineal CP (KP ) =

s−1 X

pi + c

i=1

ps ws

= 100 + 80 + 25

30 = 205 30

Dantzig s−1 X



 ps U1 = pi + c ws i=1   30 = 100 + 80 + 25 = 205 30 Martello & Toth Sin ingresar al elemento cr´ıtico: s−1 X

 ps+1 W1 = pi + c ws+1 i=1   15 = 100 + 80 + 25 20 = 180 + b18,75c = 180 + 18 = 198 

10

Ingresando al elemento cr´ıtico: s−1 X

 ps−1 W2 = pi + ps − (ws − c) ws−1 i=1   80 = 100 + 80 + 30 − (30 − 25) 20 = 180 + 10 = 190 

En consecuencia: U2 = max(W1 ; W2 ) = max(198; 190) = 198

11

4.

Variantes

Existen distintas variaciones que se han realizado al problema de la mochila est´andar. A continuaci´on se presenta una breve introducci´on a algunas de ellas. Acotado: En esta variante, en vez de contar con solamente un elemento de cada tipo, se tiene una cantidad limitada y conocida de cada uno de los elementos (que no necesariamente es la misma). Es decir, el modelo pasa a ser: x i ≤ bi n X

(∀i = 1..n)

w i xi ≤ c

i=1

max → z =

n X

p i xi

i=1

No acotado: El problema de la mochila no acotado es una instancia particular del problema de la mochila acotado en el cual cada bi = ∞ Suma de subconjuntos: Existe una variante en la cual el beneficio es igual al peso para cada uno de los elementos. Esto no implica que el beneficio (o peso) sea el mismo para cada uno de los elementos n X

w i xi ≤ c

i=1

max → z =

n X

w i xi

i=1

Problema del cambio: Hay un caso particular que aparece cuando se exige cumplir exactamente con la restricci´on de capacidad. En este caso adem´as se plantea que pi = 1 ya que se intenta reconstruir la situaci´on de un cajero que debe maximizar o minimizar la cantidad de monedas que entrega de cambio.

12

n X

w i xi = c

i=1

max → z =

n X

xi

i=1

M´ ultiples mochilas: Otra de las variantes conocidas surge de la generalizaci´on del problema est´andar, cuando en vez de tener un solo contenedor(mochila), se tienen varios. m X

xij ≤ 1

(∀ i)

wi xij ≤ cj

(∀ j)

j=1 n X i=1

max → z =

m X n X i=1 i=1

13

pi xij

5. 5.1.

Aplicaciones Merkle-Hellman:

Una de las aplicaciones m´as importantes del problema de la mochila fue en el ´area de la criptograf´ıa. En 1976, Ralph Merkle y Martin Hellman idearon un sistema muy sencillo de implementar cuya fortaleza se basaba en la dificultad de resolver el problema de la mochila. En particular, aplicaba este problema en la generaci´on de claves de un sistema criptogr´afico sim´etrico. El algoritmo se basa en la idea de que dado un n´ umero k y conjunto de n´ umeros C, el costo en t´erminos computacionales de saber cu´ales n´ umeros de C se utilizaron para sumar k es tan alto que la comunicaci´on es segura. Este sistema criptogr´afico fue utilizado durante a˜ nos especialmente debido a su simplicidad. Sin embargo, en 1982 se descubri´o un algoritmo que permite romper este sistema criptogr´afico en tiempo polinomial y en consecuencia, dejo de ser utilizado[3].

5.2.

Otras aplicaciones

Existen otras aplicaciones en distintas ´areas y que tienen distintos tipos de recurso limitante. Algunos ejemplos son: Selecci´on de oportunidades de inversi´on: presupuesto como limitante. Un estudio interesante[6] se puede encontrar que analiza situaciones en las cuales los elementos que se pueden incluir en la mochila se van recibiendo en forma continua y se debe tomar una decisi´on de que elementos elegir sin haber recibido todos (Problema de la secretaria[7]) Desperdiciar la menor cantidad de tela : material como limitante. Aprovechar al m´aximo el uso de m´aquinas: tiempo como limitante.

14

Referencias [1] MARTELLO, S. and TOTH, P. Knapsack Problems: Algorithms and Computer Implementation. 1990. [2] BARTHOLDI, J. Building Intuition: Insights From Basic Operations Management Models and Principles. 2008. [3] SHAMIR, Adi. A polynomial time algorithm for breaking the basic MerkleHellman cryptosystem. 1982. [4] KARP, Richard. Reducibility Among Combinatorial Problems. 1972. [5] Teor´ıa de la complejidad computacional. Wikipedia. http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_ computacional [6] BABAIOFF, Richard et Al. A Knapsack Secretary Problem with Applications. 2007. [7] FREEMAN, P.R. The Secretary Problem and Its Extensions: A Review. 1983.

15