Bin Packing
Problem
Luis Ramon Espinosa Cantú 1824331
Luis Enrique Santa Anna Treviño 1884211
Oziel Rafael de Leon de Leon 1815554
Melissa Elizabeth Sánchez Valdés 1671254
Alejandro Emilio López Rodríguez1659008
Bin packing Problem
Es uno de muchos problemas definidos en optimización, este
en concreto nos ayuda a minimizar el número de
contenedores en donde podemos almacenar una cantidad
limitada de objetos
Descripción del
problema
El Bin Packing Problem es un problema
np-combinatoria (Lo que quiere decir que es
combina NP y NP-hard).
Esto dado a un conjunto de ítems de tamaño
variable, se busca acomodarlos dentro de
contenedores de tamaño fijo, buscando
optimizar el número de contenedores a utilizar,
es decir, usando el menor número de
contenedores para colocar el mayor número de
ítems posible.
Problemas NP
La importancia de esta clase de
problemas de decisión es que
contiene muchos problemas de
búsqueda y de optimización para los
que se desea saber si existe una
cierta solución o si existe una mejor
solución que las conocidas.
En esta clase están el problema del
viajante donde se quiere saber si
existe una ruta óptima que pasa por
todos los nodos en un cierto grafo y
el problema de satisfacibilidad
booleana en donde se desea saber si
una cierta fórmula de lógica
proposicional puede ser cierta para
algún conjunto de valores booleanos
para las variables.
Problemas NP-Hard
NP-Hard: es el conjunto de los problemas de decisión que contiene los
problemas H tales que todo problema L en NP puede ser transformado
polinomialmente en H. Esta clase puede ser descrita como aquella que
contiene a los problemas de decisión que son como mínimo tan difíciles
como un problema de NP.
Descripción Gráfica
Puede ser observada en maneras
bidimensionales y
tridimensionales ambos muestran
la vista previa del problema
como objetos en orden y
desordenados, tanto como las
posibles soluciones que puede
tener ya que en la vista
tridimensional existen múltiples
formas más complejas de las
soluciones cercanas a la optima.
Formulación matemática
Variables
• Minimizar K=j=1nyj I: Número finito de ítems
Sujeto a K≥1, i: Ítem
j: Contenedor
s(i): El tamaño de los ítems.
B: Capacidad entera positiva del contenedor.
K: Entero positivo de la cantidad de
contenedores a usar.
Aplicaciones del
problema en casos reales
• En automóviles o camiones de carga de mercancía,
ya que se debe optimizar el espacio que hay por cada
unidad, así como la ruta que deberá seguir para la
entrega y las unidades de reparto con las que se
cuenten en el momento.
• En la selección de proyectos a trabajar, también
podemos encontrar esta función, ya que
necesitamos escoger el proyecto que nos otorgue el
mejor beneficio, en cuanto a la cantidad de personas
a involucrar, el material que será necesario, así como
los costos de estos, entre otras cosas.
Métodos de solución al problema.
Algoritmos de aproximación
• Cotas Inferiores: [Martello and Toth, 1990a]
• Heurísticas: Los algoritmos de aproximación principales fueron
descritos por [Scholl et al., 1997].
• Recocido simulado y búsqueda Tabú: La heurística Simulated
Annealing clásico implementada [Kampke, 1988].
• Heurísticas basadas en poblaciones: El primer algoritmo genético
para BPP fue propuesto en [Falkenauer and Delchambre, 1992].
Métodos Exactos
• Branch-and-bound: En este algoritmo se utilizaba el constructivo Best Fit Decreasing(BFD) y se
producía un árbol de decisión binaria donde genera dos nodos descendentes por asignación de
objetos a contenedores.
• Branch-and-price: Este se enfoca en la generación de precios y no en la generación de columnas
como el Branch-and-bound. En cada nodo de decisión, el algoritmo considera aquellas opciones
para las cuales la variable de decisión es fraccionaria y del par de elementos que derivan de ese
nodo se selecciona el de mayor peso total.
• Dynamic Programing Flow: Este modelo se obtiene de asociar los objetos a las variables de
decisión del problema clásico de programación dinámica (DP).