El problema de empaquetado en contenedores es una cuestión de optimización, en la que artículos de diferentes tamaños deben distribuirse en un conjunto de contenedores, cada uno con una capacidad fija, de forma que se minimice el número de contenedores utilizados. Este problema tiene diversas aplicaciones, como el llenado de contenedores, la carga de camiones con restricciones de capacidad de peso, la creación de archivos de copia de seguridad en medios, la división de un prefijo de red en múltiples subredes y la asignación de tecnologías en el diseño de matrices de puertas programables en campo (FPGA) en circuitos integrados.
Computacionalmente, el problema es NP-difícil, y el correspondiente problema de decisión, que dilucida si los elementos caben en un número específico de contenedores, es NP-completo. A pesar de su dificultad en el peor de los casos, se pueden producir soluciones óptimas para instancias muy grandes del problema con algoritmos sofisticados. Además, existen muchos algoritmos de aproximación. Por ejemplo, el algoritmo First-Fit proporciona una solución rápida, pero a menudo no óptima, que implica colocar cada elemento en el primer contenedor en el que quepa. Requiere un tiempo Θ(n log n), donde n es el número de elementos a empaquetar. El algoritmo puede hacerse mucho más efectivo ordenando primero la lista de elementos en orden decreciente (a veces conocido como el algoritmo decreciente de primer ajuste), aunque esto todavía no garantiza una solución óptima y para listas más largas puede aumentar el tiempo de ejecución del algoritmo. Sin embargo, se sabe que siempre existe al menos un ordenamiento de elementos que permite que el primer ajuste produzca una solución óptima.
Existen muchas variaciones de este problema, como el empaquetado 2D, el empaquetado lineal, el empaquetado por peso, el empaquetado por costo y otros. El problema del empaquetado en contenedores también puede considerarse un caso especial del problema de corte de valores. Cuando el número de contenedores se limita a uno y cada elemento se caracteriza por un volumen y un valor, el problema de maximizar el valor de los elementos que caben en el contenedor se conoce como problema de la mochila.
Una variante del empaquetado en contenedores que se da en la práctica es cuando los elementos pueden compartir espacio al empaquetarse en un contenedor. Específicamente, un conjunto de elementos podría ocupar menos espacio al empaquetarse juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaquetado de máquinas virtuales (MV), ya que cuando se empaquetan máquinas virtuales (MV) en un servidor, su requerimiento de memoria total podría disminuir debido a que hay páginas compartidas por las MV que solo necesitan almacenarse una vez. Si los elementos pueden compartir espacio de forma arbitraria, el problema del empaquetado en contenedores es difícil de aproximar. Sin embargo, si el espacio compartido se jerarquiza, como ocurre con el uso compartido de memoria en máquinas virtuales, el problema del empaquetado en contenedores se puede aproximar eficientemente.
Otra variante del empaquetado en contenedores de interés en la práctica es el llamado empaquetado en contenedores en línea. En este caso, se supone que los artículos de diferente volumen llegan secuencialmente, y quien toma la decisión debe decidir si selecciona y empaqueta el artículo observado actualmente o lo deja pasar. Cada decisión no se puede revertir. Por el contrario, el empaquetado en contenedores fuera de línea permite reorganizar los artículos con la esperanza de lograr un mejor empaquetado cuando lleguen artículos adicionales. Esto, por supuesto, requiere almacenamiento adicional para depositar temporalmente los artículos que se reorganizarán más adelante.
Enunciado formal En Computers and Intractability: A Guide to the Theory of NP-Completeness, Garey y Johnson enumeran el problema de empaquetado en contenedores bajo la referencia [SR1]. Definen su variante de decisión de la siguiente manera:
Ejemplo: Conjunto finito de artículos, un tamaño para cada , una capacidad de contenedor entera positiva y un entero positivo .
Pregunta: ¿Existe una partición de en conjuntos disjuntos tal que la suma de los tamaños de los artículos en cada sea o menor?
Cabe destacar que en la literatura se utiliza a menudo una notación equivalente, donde y para cada . Además, la investigación se centra principalmente en la variante de optimización, que busca el valor más pequeño posible de . Una solución es óptima si tiene un mínimo. El valor de para una solución óptima para un conjunto de elementos se denota por o simplemente si el conjunto de elementos se desprende del contexto.
Una posible formulación del problema en programación lineal entera es: Minimizar sujeto a que donde si se utiliza el contenedor y si el elemento se coloca en el contenedor .
Dificultad del empaquetado en contenedores El problema del empaquetado en contenedores es difícilmente NP-completo. Esto se puede demostrar reduciendo el problema de la 3-partición difícilmente NP-completo al empaquetado en contenedores.
Además, no puede haber ningún algoritmo de aproximación con una razón de aproximación absoluta menor que , a menos que . Esto se puede demostrar mediante una reducción al problema de la partición. Dada una instancia de partición en la que la suma de todos los números de entrada es , se construye una instancia de empaquetado en contenedores cuyo tamaño sea . Si existe una partición equitativa de las entradas, el empaquetado óptimo necesita 2 contenedores; por lo tanto, todo algoritmo con una razón de aproximación menor que debe devolver menos de 3 contenedores, lo que debe ser 2 contenedores. Por el contrario, si no existe una partición equitativa de las entradas, el empaquetado óptimo necesita al menos 3 contenedores.
Por otro lado, el empaquetado en contenedores se puede resolver en tiempo pseudopolinómico para cualquier número fijo de contenedores , y en tiempo polinomial para cualquier capacidad fija de los contenedores .
Algoritmos de aproximación para el empaquetado en contenedores Para medir el rendimiento de un algoritmo de aproximación, en la literatura sobre el tema se consideran dos ratios de aproximación. Para una lista dada de elementos , el número denota el número en contenedores utilizados cuando el algoritmo se aplica a la lista , mientras que denota el número óptimo para esta lista. El ratio de rendimiento absoluto en el peor caso para un algoritmo se define como:
Por otro lado, el ratio asintótico en el peor caso se define como:
Equivalentemente, es el número más pequeño tal que existe una constante K, tal que para todas las listas L:.
Además, se pueden restringir las listas a aquellas cuyos elementos tengan un tamaño máximo de . Para estas listas, los índices de rendimiento de tamaño acotado se denotan como y .
Los algoritmos de aproximación para el empaquetado en contenedores se pueden clasificar en dos categorías:
Heurísticas en línea, que consideran los elementos en un orden determinado y los colocan uno a uno dentro de los contenedores. Estas heurísticas también son aplicables a la versión fuera de línea de este problema. Heurísticas fuera de línea, que modifican la lista de elementos dada, por ejemplo, ordenándolos por tamaño. Estos algoritmos ya no son aplicables a la variante en línea de este problema. Sin embargo, ofrecen una garantía de aproximación mejorada, manteniendo la ventaja de su baja complejidad temporal. Una subcategoría de las heurísticas fuera de línea son los esquemas de aproximación asintótica. Estos algoritmos tienen una garantía de aproximación de la forma para alguna constante que puede depender de . Para un valor arbitrario de , estos algoritmos se aproximan arbitrariamente a . Sin embargo, esto conlleva una complejidad temporal (drásticamente) mayor en comparación con los enfoques heurísticos.
Heurísticas en línea En la versión en línea del problema de empaquetado en contenedores, los artículos llegan uno tras otro y la decisión (irreversible) de dónde colocar un artículo debe tomarse antes de conocer el siguiente o incluso si habrá otro. David S. Johnson ha estudiado un conjunto diverso de heurísticas en línea y fuera de línea para el empaquetado en contenedores en su tesis doctoral.
Algoritmos de clase única Existen muchos algoritmos simples que utilizan el siguiente esquema general: Para cada elemento de la lista de entrada: Si el elemento cabe en uno de los contenedores abiertos, colóquelo en uno de ellos. En caso contrario, abra un nuevo contenedor y coloque el nuevo elemento en él
Los algoritmos difieren en el criterio con el que eligen el contenedor abierto para el nuevo elemento en el paso 1 (consúltense las páginas enlazadas para obtener más información):
Next Fit (NF) siempre mantiene un único contenedor abierto. Cuando el nuevo elemento no cabe en él, cierra el contenedor actual y abre uno nuevo. Su ventaja es que es un algoritmo de espacio acotado, ya que solo necesita mantener un único contenedor abierto en memoria. Su desventaja es que su razón de aproximación asintótica es 2. En particular, , y para cada existe una lista tal que y . Su razón de aproximación asintótica se puede mejorar ligeramente según los tamaños de los elementos: para todos los y para todos los . Para cada algoritmo ( que sea un algoritmo AnyFit, se cumple . Next-k-Fit (NkF) es una variante de Next-Fit, pero en lugar de mantener solo un intervalo abierto, el algoritmo mantiene abiertos los últimos intervalos y elige el primero en el que encaja el elemento. Por lo tanto, se denomina algoritmo de espacio k-acotado. Para , el método NkF ofrece resultados mejorados en comparación con los resultados del método NF. Sin embargo, aumentar a valores constantes mayores que no mejora aún más el algoritmo en su peor caso. Si el algoritmo es un algoritmo AlmostAnyFit (de "CasiCualquierAjuste) y , entonces . First-Fit (FF) mantiene todos los contenedores abiertos, en el orden en que se abrieron. Intenta colocar cada elemento nuevo en el primer contenedor en el que encaja. Su razón de aproximación es , y existe una familia de listas de entrada para las cuales coincide con este límite. Best-Fit (BF) también mantiene todos los contenedores abiertos, en el orden en que se abrieron. Pero intenta colocar cada nuevo elemento en el contenedor en el que encaje que esté más cargado. Su razón de aproximación es , y existe una familia de listas de entrada para las cuales coincide con este límite.Worst-Fit (WF) (peor llenado) intenta colocar cada nuevo elemento en el contenedor menos lleno. Puede comportarse tan mal como el Next-Fit, y lo hará en la lista de peores casos para . Además, cumple que . Dado que el WF es un algoritmo AnyFit, existe un algoritmo AnyFit tal que . Almost Worst-Fit (AWF) (casi peor llenado) intenta colocar cada elemento nuevo dentro del segundo contenedor abierto más vacío (o el contenedor más vacío si hay dos). Si no encaja, prueba con el más vacío. Su razón asintótica de peor caso es . Para generalizar estos resultados, Johnson introdujo dos clases de heurísticas en línea denominadas algoritmos de ajuste aleatorio y algoritmos de ajuste casi aleatorio: En un algoritmo AnyFit (AF), si los contenedores actuales no vacíos son B1,..., Bj, el elemento actual no se empaquetará en Bj+1 a menos que no encaje en ninguno de los siguientes B1,..., Bj. Los algoritmos FF, WF, BF y AWF satisfacen esta condición. Johnson demostró que, para cualquier algoritmo A AnyFit y cualquier : . En un algoritmo "AlmostAnyFit (AAF)", si los contenedores no vacíos actuales son "B"1,..., "Bj", y de estos contenedores, "Bk" es el único con la carga más pequeña, el elemento actual no se empaquetará en "Bk", a menos que no quepa en ninguno de los contenedores a su izquierda. Los algoritmos FF, BF y AWF cumplen esta condición, pero WF no. Johnson demostró que, para cualquier algoritmo A AAF y cualquier :