Problema con la cubierta del contenedor

Problema de investigación de operaciones de empaquetar artículos en el mayor número de contenedores

En el problema de cubrimiento de contenedores , los artículos de diferentes tamaños deben empaquetarse en un número finito de contenedores, cada uno de los cuales debe contener al menos un cierto tamaño total dado, de manera que se maximice el número de contenedores utilizados.

Este problema es una versión dual del problema de empaquetamiento de contenedores : en el cubrimiento de contenedores, los tamaños de los contenedores están limitados desde abajo y el objetivo es maximizar su número; en el empaquetamiento de contenedores, los tamaños de los contenedores están limitados desde arriba y el objetivo es minimizar su número. ^[1]

El problema es NP-hard , pero existen varios algoritmos de aproximación eficientes :

• Los algoritmos que cubren al menos 1/2, 2/3 o 3/4 del bin óptimo cuentan de manera asintótica y se ejecutan en el tiempo respectivamente. ^{[1] [2]} ${\displaystyle O(n),O(n\log n),O(n{\log }^{2}n)}$
• Un PTAS asintótico , algoritmos con un comportamiento acotado en el peor de los casos cuyo comportamiento esperado es asintóticamente óptimo para algunas distribuciones discretas, y un algoritmo de aprendizaje con un comportamiento esperado asintóticamente óptimo para todas las distribuciones discretas. ^[3]
• Un FPTAS asintótico . ^[4]

El algoritmo de llenado de contenedores bidireccional

Csirik, Frenk, Lebbe y Zhang ^{[2] : 16–19} presentan el siguiente algoritmo simple para la aproximación 2/3. Supongamos que el tamaño del contenedor es 1 y hay n elementos.

• Ordena los elementos del más grande (1) al más pequeño ( n ).
• Llene un contenedor con los elementos más grandes : 1, 2, ..., m , donde m es el entero más grande para el cual la suma de los elementos 1, ..., m es menor que 1.
• Añade a este contenedor los elementos más pequeños : n , n -1, ..., hasta que su valor supere 1.

Para cualquier instancia I , denotamos por el número de contenedores en la solución óptima y por el número de contenedores llenos en el algoritmo de llenado bidireccional. Entonces , o equivalentemente, . ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {BDF} (I)}$ ${\displaystyle \mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)}$ ${\displaystyle \mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1}$

Prueba

Para la prueba se utiliza la siguiente terminología:

• ${\displaystyle t:=\mathrm {BDF} (I)=}$el número de contenedores llenados por el algoritmo.
• ${\displaystyle B_{1},\ldots ,B_{t}:=}$los contenedores t llenados por el algoritmo.
• Elementos iniciales : los t elementos que se insertan primero en cada uno de los t contenedores.
• Elementos finales : los t elementos que se insertan por último en cada uno de los t contenedores.
• Elementos intermedios : todos los elementos que no son ni iniciales ni finales.
• ${\displaystyle w}$ := el número de elementos finales que son como máximo 1/2 (equivalentemente, es el número de elementos finales mayores que 1/2). ${\displaystyle t-w}$

La suma de cada contenedor es al menos 1, pero si se elimina el último elemento, la suma restante es menor que 1. Cada uno de los primeros contenedores contiene un elemento inicial, posiblemente algunos elementos intermedios y un elemento final. Cada uno de los últimos contenedores contiene solo un elemento inicial y un elemento final, ya que ambos son mayores que 1/2 y su suma ya es mayor que 1. ${\displaystyle B_{1},\ldots ,B_{t}}$ ${\displaystyle w}$ ${\displaystyle B_{1},\ldots ,B_{w}}$ ${\displaystyle t-w}$ ${\displaystyle B_{w+1},\ldots ,B_{t}}$

La prueba considera dos casos.

El caso fácil es , es decir, todos los elementos finales son menores que 1/2. Entonces, la suma de cada elemento lleno es como máximo 3/2, y la suma de los elementos restantes es como máximo 1, por lo que la suma de todos los elementos es como máximo . Por otro lado, en la solución óptima la suma de cada contenedor es al menos 1, por lo que la suma de todos los elementos es al menos . Por lo tanto, como se requiere. ${\displaystyle w=t}$ ${\displaystyle B_{i}}$ ${\displaystyle 3t/2+1}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} (I)\leq 3t/2+1}$

El caso difícil es , es decir, algunos elementos finales son mayores que 1/2. Ahora demostramos un límite superior de presentándolo como una suma donde: ${\displaystyle w<t}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|}$

• ${\displaystyle K_{0}:=}$los contenedores óptimos sin elementos iniciales/finales (solo elementos intermedios).
• ${\displaystyle K_{1}:=}$los contenedores óptimos con exactamente un artículo inicial/final (y algunos artículos intermedios).
• ${\displaystyle K_{2}:=}$los contenedores óptimos con dos o más elementos iniciales/finales (y algunos elementos intermedios).

Nos centramos primero en los contenedores óptimos en y . Presentamos una biyección entre los artículos en cada uno de esos contenedores hasta algunos artículos en los que son al menos tan valiosos. ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{t}}$

• El elemento inicial/final único en los contenedores se asigna al elemento inicial en . Tenga en cuenta que estos son los elementos iniciales más grandes. ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$
• Los elementos del medio en los contenedores y se asignan a los elementos del medio en . Tenga en cuenta que estos contenedores contienen todos los elementos del medio. ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{w}}$
• Por lo tanto, todos los elementos en y se asignan a todos los elementos no finales en , más todos los elementos intermedios en . ${\displaystyle K_{0}}$ ${\displaystyle K_{1}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$ ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$
• La suma de cada contenedor sin su elemento final es menor que 1. Además, el elemento inicial es mayor que 1/2, por lo que la suma de solo los elementos intermedios es menor que 1/2. Por lo tanto, la suma de todos los elementos no finales en , más todos los elementos intermedios en , es como máximo . ${\displaystyle B_{1},\ldots ,B_{w}}$ ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$ ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$ ${\displaystyle |K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2}$
• La suma de cada contenedor óptimo es al menos 1. Por lo tanto: , lo que implica . ${\displaystyle |K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2}$ ${\displaystyle 2|K_{0}|+|K_{1}|\leq w\leq t}$

Ahora nos centraremos en los contenedores óptimos en y . ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$

• El número total de elementos iniciales/finales en los contenedores y es al menos , pero su número total también es , ya que hay exactamente dos elementos iniciales/finales en cada contenedor. Por lo tanto, . ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$ ${\displaystyle |K_{1}|+2|K_{2}|}$ ${\displaystyle 2t}$ ${\displaystyle |K_{1}|+2|K_{2}|\leq 2t}$
• Sumar las dos últimas desigualdades implica que , lo que implica . ${\displaystyle 2\mathrm {OPT} (I)\leq 3t}$ ${\displaystyle \mathrm {OPT} (I)\leq 3t/2}$

Opresión

El factor 2/3 es ajustado para BDF. Consideremos el siguiente ejemplo (donde es suficientemente pequeño): BDF inicializa el primer contenedor con el elemento más grande y lo llena con los elementos más pequeños. Luego, los elementos restantes pueden cubrir contenedores solo en tripletes, por lo que todos los contenedores están llenos. Pero en OPT se pueden llenar contenedores, cada uno de los cuales contiene dos de los elementos de tamaño mediano y dos elementos pequeños. ${\displaystyle \epsilon >0}$ $${\displaystyle {\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 6k~{\text{units}}\cdots \}~&~\{\cdots 6k~{\text{units}}\cdots \}\end{aligned}}}$$ ${\displaystyle 6k}$ ${\displaystyle 6k}$ ${\displaystyle 2k+1}$ ${\displaystyle 3k}$

Algoritmo de llenado de contenedores de tres clases

Csirik, Frenk, Lebbe y Zhang ^{[2] : 19–24} presentan otro algoritmo que logra una aproximación de 3/4. El algoritmo ordena los elementos de mayor a menor y los divide en tres clases:

• X: Los artículos con tamaño al menos 1/2;
• Y: Los artículos con tamaño menor a 1/2 y al menos 1/3;
• Z: Los artículos con tamaño menor a 1/3.

El algoritmo funciona en dos fases. Fase 1:

• Inicialice un nuevo contenedor con el elemento más grande de X o con los dos elementos más grandes de Y, el que sea mayor. Tenga en cuenta que, en ambos casos, la suma inicial del contenedor es menor que 1.
• Llene el nuevo contenedor con artículos del orden Z en orden creciente de valor.
• Repita hasta que XUY o Z estén vacíos.

Fase 2:

• Si XUY está vacío, llene los contenedores con elementos de Z mediante la simple regla del siguiente ajuste.
• Si Z está vacío, empaque los elementos que quedan en X en pares, y los que quedan en Y en tripletes.

En el ejemplo anterior, que muestra la estrechez de BDF, los conjuntos son: TCF alcanza el resultado óptimo, ya que inicializa todos los contenedores con pares de elementos de Y y los llena con pares de elementos de Z. $${\displaystyle {\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{|X|=1\}~&~\{\cdots |Y|=6k\cdots \}~&~\{\cdots |Z|=6k\cdots \}\end{aligned}}}$$ ${\displaystyle 3k}$

Para cualquier instancia I , denotamos por el número de contenedores en la solución óptima y por el número de contenedores llenos en el algoritmo de llenado de tres clases. Entonces . ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {TCF} (I)}$ ${\displaystyle \mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)}$

El factor 3/4 es ajustado para TCF. Consideremos el siguiente ejemplo (donde es suficientemente pequeño): ${\displaystyle \epsilon >0}$

$${\displaystyle {\begin{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{units}}\cdots \}~&~\{\cdots 12k~{\text{units}}\cdots \}\end{aligned}}}$$

TCF inicializa el primer contenedor con los dos elementos más grandes y lo llena con los elementos más pequeños. Luego, los elementos restantes pueden cubrir contenedores solo en grupos de cuatro, por lo que todos los contenedores están llenos. Pero en OPT se pueden llenar contenedores, cada uno de los cuales contiene 3 elementos de tamaño mediano y 3 elementos pequeños. ${\displaystyle 12k}$ ${\displaystyle 12k}$ ${\displaystyle 3k+1}$ ${\displaystyle 4k}$

Esquemas de aproximación en tiempo polinomial

Csirik, Johnson y Kenyon ^[3] presentan un PTAS asintótico. Es un algoritmo que, para cada ε >0, llena al menos bins si la suma de todos los elementos es mayor que , y al menos en caso contrario. Se ejecuta en tiempo . El algoritmo resuelve una variante del programa lineal de configuración , con variables y restricciones. Este algoritmo solo es interesante teóricamente, ya que para obtener una aproximación mejor que 3/4, debemos tomar , y entonces el número de variables es mayor que . ${\displaystyle (1-5\varepsilon )\cdot \mathrm {OPT} (I)-4}$ ${\displaystyle 13B/\epsilon ^{3}}$ ${\displaystyle (1-2\varepsilon )\cdot \mathrm {OPT} (I)-1}$ ${\displaystyle O(n^{1/\varepsilon ^{2}})}$ ${\displaystyle n^{1/\varepsilon ^{2}}}$ ${\displaystyle 1+1/\varepsilon ^{2}}$ ${\displaystyle \varepsilon <1/20}$ ${\displaystyle n^{400}}$

También presentan algoritmos para la versión en línea del problema. En el entorno en línea, no es posible obtener un factor de aproximación asintótico para el peor de los casos mejor que 1/2. Sin embargo, hay algoritmos que funcionan bien en el caso promedio.

Jansen y Solis-Oba ^[4] presentan un FPTAS asintótico. Es un algoritmo que, para cada ε >0, llena al menos bins si la suma de todos los elementos es mayor que (si la suma de los elementos es menor que eso, entonces el óptimo es como máximo de todos modos). Se ejecuta en tiempo , donde es la complejidad en tiempo de ejecución del mejor algoritmo disponible para inversión de matrices (actualmente, alrededor de ). Este algoritmo se vuelve mejor que la aproximación 3/4 ya cuando , y en este caso las constantes son razonables - alrededor de . ${\displaystyle (1-\varepsilon )\cdot \mathrm {OPT} (I)-1}$ ${\displaystyle 13B/\epsilon ^{3}}$ ${\displaystyle 13/\epsilon ^{3}\in O(1/\epsilon ^{3})}$ ${\displaystyle O\left({\frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilon ^{4}}}{\mathcal {T_{M}}}({\frac {1}{\varepsilon ^{2}}})\right)}$ ${\displaystyle {\mathcal {T_{M}}}(n)}$ ${\displaystyle O(n^{2.38})}$ ${\displaystyle \varepsilon <1/4}$ ${\displaystyle 2^{10}n^{2}+2^{18}}$

Rendimiento con tamaños de elementos divisibles

Un caso especial importante de cubrimiento de bins es que los tamaños de los elementos forman una secuencia divisible (también llamada factorizada ). Un caso especial de tamaños de elementos divisibles ocurre en la asignación de memoria en sistemas informáticos, donde los tamaños de los elementos son todos potencias de 2. Si los tamaños de los elementos son divisibles, entonces algunos de los algoritmos heurísticos para el cubrimiento de bins encuentran una solución óptima. ^{[5] : Sec.5}

Problemas relacionados

En el problema de asignación justa de elementos , hay distintas personas que atribuyen un valor diferente a cada elemento. El objetivo es asignar a cada persona un "recipiente" lleno de elementos, de modo que el valor de cada uno de ellos sea al menos una constante determinada, y que el mayor número posible de personas reciba un recipiente. En este problema también se utilizan muchas técnicas de cobertura de recipientes.

Implementaciones

• Python: El paquete prtpy contiene una implementación de los algoritmos Csirik-Frenk-Labbe-Zhang.

Referencias

1. Assmann, S. F; Johnson, D. S; Kleitman, D. J; Leung, JY -T (1984-12-01). "Sobre una versión dual del problema de empaquetamiento de bins unidimensional". Journal of Algorithms . 5 (4): 502–525. doi :10.1016/0196-6774(84)90004-X. ISSN  0196-6774.
2. Csirik, János; JBG Frenk y M. Labbé y S. Zhang (1999-01-01). "Dos algoritmos simples para cubrir bins". Acta Cybernetica . 14 (1): 13–25. ISSN  2676-993X.
3. Csirik, Janos; Johnson, David S.; Kenyon, Claire (9 de enero de 2001). "Mejores algoritmos de aproximación para el cubrimiento de bins". Actas del duodécimo simposio anual ACM-SIAM sobre algoritmos discretos . SODA '01. Washington, DC, EE. UU.: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.
4. Jansen, Klaus; Solis-Oba, Roberto (21 de noviembre de 2002). "Un esquema de aproximación temporal totalmente polinomial asintótico para el cubrimiento de bins". Actas del 13.º Simposio Internacional sobre Algoritmos y Computación . ISAAC '02. 2518. Berlín, Heidelberg: Springer-Verlag: 175–186. doi :10.1007/3-540-36136-7_16. ISBN 978-3-540-00142-3.
5. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de elementos divisibles". Journal of Complexity . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.