Reporte 2: Problema de la mochila.

El problema de la mochila, tambien llamado knapsack problem, es un problema que modela la situación de llenar una mochila, limitada a cierta capacidad de peso y con cierta cantidad de objetos con diferentes pesos y valores cada uno. Los objetos que se pongan en la mochila deben de maximizar el valor total, sin superar el peso máximo permitido. Es uno de los 21 problemas NP-completos de Richard Karp.

El problema de la mochila: ¿Que cubos debemos elegir
 para maximizar la cantidad sin sobrepasar los 15 kg permitidos?

El problema de la mochila tiene sus puntos relevantes:

• Hay un algoritmo pseudo-polinomial (ya que ahora la salida es polinomial), con programación dinamica.
• Hay un aproximación de tiempo polinomial completo, utilizando el algoritmo anterior como subrutina
• El problema es NP-completo, por lo que se espera que ningún algoritmo puede ser rapido y correcto (en tiempo polinomial) en todos los casos.

Los datos del problema se pueden expresar en términos matemáticos. 

• Los objetos están numerados por el índice i variando de 1 a n. 
• Los números wi y pi representan el peso y el valor del número i. 
• La capacidad de la bolsa se denomina en esta formula W.

Existen muchas manera de llenar la mochila, para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, pudiendo utilizar el código binario que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera, y para ir llenando esta mochila podemos utilizar un vector de contenido, que comprende: X = (x1, x2, ..., xn), entonces podemos expresar una función del contenido del vector.

Para un contenido dado X, el valor total de la bolsa es:

De la misma manera, la suma de los pesos de los objetos es:

El problema entonces lo podemos enunciar como un contenido de vectores X = (x1, x2, ..., xn), que tienen componentes de ceros y unos, teniendo como máximo la restricción de la función z(X).

Esto quiere decir que la suma de los pesos (o sea, la función w(X)), de los objetos que pusimos en la mochila no deben de superar la capacidad de esta, (o sea, la W).

Podemos decir que:

• z(X) es una función objetivo (como su nombre lo dice, representa el objetivo del problema, esta expresión se maximiza o se minimiza.
• Un vector X que cumple con la restricción W en la tercera formula se le nombra factible (o sea, que se pude hacer).
• Si tenemos un resultado máximo en z(X), entonces X es óptimo.

Se le pueden agregar otras restricciones según tengamos un caso, en esta liga, encontramos diferentes casos singulares.

Con esto podemos argumentar que tenemos un problema de decisión cuando para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera y podemos decir que es un problema de optimización porque podemos encontrar funciones objetivo, valores óptimos utilizando las declaraciones matemáticas.

El problema es NP-completo porque se puede representar como una toma de decisiones mediante el reemplazo del máximo, utilizando la siguiente pregunta: 

Dado el número k, existe un valor xi para el cual  

Existe un vinculo entre la version de decisión y la version de optimización del problema en que si existe un algoritmo polinomial que resuelve la versión de decisión,  por lo tanto, las dos versiones del problema son de dificultad similar.

El problema de optimización es NP-hard, su resolución es al menos tan difícil como el problema de decisión.

La prueba de que el problema es NP-completo fue presentado por Michail G. Lagoudakis, se puede encontrar en la misma liga

Algoritmos existentes:
Algoritmo Greddy o voraz: La idea es añadir un objeto prioritario mas efectivo hasta la saturación de la mochila. La complejidad de estos algoritmos se basa en la inversa de la calidad esperada.

Las dos fases del algoritmo voraz

Podemos ver las dos fases del algoritmo voraz.
      A) el ordenamiento de las cajas según un interes (en este caso en peso en $/kg)
      B) si es posible la entrar a la mochila.  




Algoritmo genético: se utiliza a menudo en problemas de optimización difíciles, como este, facil de implementar y obtener rapidamente una solución.

 

Ejemplo de la evolución de una población con
un algoritmo genetico.

Los objetos son utilizados para el algoritmo voraz, por ejemplo el genoma (0,1,0,0,0) corresponde a un cuadro de selección de 12 kg de peso 7.




Programación dinámica: El problema de la mochila tiene la propiedad que le permite utilizar el metodo de resolución de programación dinámica.
Este algoritmo tiene una complejidad en tiempo y espacio que tiene como ventajas la velocidad y no hay necesidad de ordenar las variables, pero como desventajas es que gasta mucha memoria, por lo tanto no puede ser solución para problemas grandes.

Aplicaciones en la vida real:

En la vida real, se utiliza para modelar diferentes situaciones:

• en los sistemas de apoyo a las fianzas: para encontrar el mejor equilibrio entre el capital y rendimiento financiero.
• en la carga del barco o avión: todo el equipaje debe ser llevado, sin ser sobrecargado.
• en el corte de materiales: para minimizar las caídas.
• entre otras...

Reducción:

El problema de la mochila, es un caso especial del SUBSET SUM, que viene de la reducción de 3-SAT, VERTEX COVER, en este PDF, vienen las reducciones hechas por Richard M. Karp de los 21 problemas, de la Universidad de Berkeley en los que se encuentra el problema de la mochila (knapsack). 

Referencias:

El Problema de la mochila, Universidad de Murcia. aqui.
Diapositivas de la clase: Optimización combinatoria. aqui.
Lecture: The knapsack problem. Technische Universiteit Eindhoven. aqui.
Reducibility among combinatorial problems de Richard M. Karp. aqui.
Encontré mucha información. aqui.

Este video me ayudó a entender la matemática, tiene subtítulos en español es del MIT.