Problema de reparto en contenedores

En el problema de reparto en contenedores, se deben distribuir artículos de diferentes tamaños en una serie de contenedores, teniendo en cuenta que cada uno de ellos debe contener uno o varios elementos que completen al menos un tamaño mínimo determinado, de forma que se maximice el número total de contenedores utilizados.

Un ejemplo sería obtener el máximo número posible de cestas de regalo cuyo contenido supere un valor mínimo, a partir de una serie de productos de diferentes precios disponibles en distintas cantidades.

Este problema es el dual del problema de empaquetado en contenedores: en el problema del reparto en contenedores, el objetivo es maximizar su número imponiendo el volumen mínimo del conjunto de artículos que debe alojar cada uno; mientras que en el problema del empaquetado en contenedores, el objetivo es minimizar el número de contenedores necesario para alojar todos los artículos.^[1]​

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

• Algoritmos que cubren al menos la mitad, dos tercios o tres cuartos del recuento óptimo de contenedores de forma asintótica, ejecutándose en el tiempo ${\displaystyle O(n),O(n\log n),O(n{\log }^{2}n)}$ respectivamente.^[1]​^[2]​
• Un esquema de aproximación de tiempo polinómico (PTAS) asintótico, algoritmos con 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 comportamiento esperado asintóticamente óptimo para todas las distribuciones discretas.^[3]​
• Un esquema de aproximación de tiempo completamente polinómico (FPTAS) asintótico.^[4]​

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

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

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

Para la demostración, se utiliza la siguiente terminología:

• ${\displaystyle t:=\mathrm {BDF} (I)=}$ el número de contenedores completados por el algoritmo.
• ${\displaystyle B_{1},\ldots ,B_{t}:=}$ los t contenedores completados 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 al final de 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, ${\displaystyle t-w}$ es el número de elementos finales mayores que 1/2).

La suma de cada contenedor ${\displaystyle B_{1},\ldots ,B_{t}}$ es al menos 1, pero si se elimina el elemento final, la suma restante es menor que 1. Cada uno de los primeros contenedores ${\displaystyle w}$ ${\displaystyle B_{1},\ldots ,B_{w}}$ contiene un elemento inicial, posiblemente algunos elementos intermedios y un elemento final. Cada uno de los últimos contenedores ${\displaystyle t-w}$ ${\displaystyle B_{w+1},\ldots ,B_{t}}$ 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.

La demostración considera dos casos.

El caso fácil es ${\displaystyle w=t}$, es decir, todos los elementos finales son menores que 1/2. Entonces, la suma de cada ${\displaystyle B_{i}}$ completado 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 ${\displaystyle 3t/2+1}$. 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 ${\displaystyle \mathrm {OPT} (I)}$. Por lo tanto, ${\displaystyle \mathrm {OPT} (I)\leq 3t/2+1}$ es lo requerido.

El caso difícil es ${\displaystyle w<t}$, es decir, algunos elementos finales son mayores que 1/2. Ahora se demuestra la existencia de una cota superior en ${\displaystyle \mathrm {OPT} (I)}$ presentándola como una suma ${\displaystyle \mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|}$ donde:

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

Primero hay que centrarse en los contenedores óptimos en ${\displaystyle K_{0}}$ y ${\displaystyle K_{1}}$. Se establece una biyección entre los elementos en cada contenedor para algunos elementos en ${\displaystyle B_{1},\ldots ,B_{t}}$ que son al menos evaluables.

• El elemento inicial/final de las categorías ${\displaystyle K_{1}}$ se asigna al elemento inicial de ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$. Se debe tener en cuenta que estos son los elementos iniciales más grandes.
• Los elementos intermedios de las categorías ${\displaystyle K_{0}}$ y ${\displaystyle K_{1}}$ se asignan a los elementos intermedios de ${\displaystyle B_{1},\ldots ,B_{w}}$, considerando que estas categorías contienen todos los elementos intermedios.
• Por lo tanto, todos los elementos de ${\displaystyle K_{0}}$ y ${\displaystyle K_{1}}$ se asignan a todos los elementos no finales de ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$, más todos los elementos intermedios de ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$.
• La suma de cada categoría ${\displaystyle B_{1},\ldots ,B_{w}}$ 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 de ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$, más todos los elementos intermedios de ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$, es como máximo ${\displaystyle |K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2}$.
• La suma de cada categoría óptima es al menos 1. Por lo tanto: ${\displaystyle |K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2}$, lo que implica ${\displaystyle 2|K_{0}|+|K_{1}|\leq w\leq t}$. Ahora, se pon el foco en los contenedores óptimos en ${\displaystyle K_{1}}$ y ${\displaystyle K_{2}}$.
• El número total de elementos iniciales/finales en los contenedores ${\displaystyle K_{1}}$ y ${\displaystyle K_{2}}$ es al menos ${\displaystyle |K_{1}|+2|K_{2}|}$, pero su número total también es ${\displaystyle 2t}$, ya que hay exactamente dos elementos iniciales/finales en cada contenedor. Por lo tanto, ${\displaystyle |K_{1}|+2|K_{2}|\leq 2t}$.
• La suma de las dos últimas desigualdades implica que ${\displaystyle 2\mathrm {OPT} (I)\leq 3t}$, lo que a su vez conlleva que ${\displaystyle \mathrm {OPT} (I)\leq 3t/2}$.

El factor 2/3 es ajustado para BDF. Considérese la siguiente instancia (donde ${\displaystyle \epsilon >0}$ es suficientemente pequeño):

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

BDF inicializa el primer contenedor con el elemento más grande y lo completa con los ${\displaystyle 6k}$ elementos más pequeños. En consecuencia, los elementos restantes ${\displaystyle 6k}$ solo pueden cubrir contenedores en tripletes, por lo que, en total, se completan ${\displaystyle 2k+1}$ contenedores. Sin embargo, en OPT se pueden completar ${\displaystyle 3k}$ contenedores, cada uno de los cuales contiene dos elementos medianos y dos pequeños.

'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: Elementos con un tamaño de al menos 1/2;
• Y: Elementos con un tamaño menor a 1/2 y al menos 1/3;
• Z: Elementos con un tamaño menor a 1/3.

El algoritmo funciona en dos fases:

Fase 1:

• Inicializar 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. Téngase en cuenta que, en ambos casos, la suma inicial de los contenedores es menor que 1.
• Completar el nuevo contenedor con elementos de Z en orden creciente de valor.
• Repetir hasta que X U Y o Z estén vacíos.

Fase 2:

• Si X U Y está vacío, completar los contenedores con elementos de Z mediante la regla simple del siguiente ajuste.
• Si Z está vacío, destinar los elementos restantes en X por pares y los restantes en Y por tripletes.

En el ejemplo anterior, que muestra la estrechez de BDF, los conjuntos son:

${\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}}}$

TCF alcanza el resultado óptimo, ya que inicializa todos los contenedores ${\displaystyle 3k}$ con pares de elementos de Y y los completa con pares de elementos de Z.

Para cualquier instancia I, denótese ${\displaystyle \mathrm {OPT} (I)}$ como el número de contenedores en la solución óptima y ${\displaystyle \mathrm {TCF} (I)}$ como el número de contenedores completados con el algoritmo de reparto con tres clases de artículos. Luego, ${\displaystyle \mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)}$.

El factor 3/4 determina la estrechez para el procedimiento TCF. Considérese el siguiente ejemplo (donde ${\displaystyle \epsilon >0}$ es suficientemente pequeño):

${\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}}}$

El TCF inicializa el primer contenedor con los dos elementos más grandes y lo completa con los ${\displaystyle 12k}$ elementos más pequeños. Entonces, los ${\displaystyle 12k}$ elementos restantes solo pueden cubrir contenedores en grupos de cuatro, por lo que, en total, se completan ${\displaystyle 3k+1}$ contenedores. Sin embargo, con la técnica OPT se pueden completar ${\displaystyle 4k}$ contenedores, cada uno con 3 elementos medianos y 3 pequeños.

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

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

Jansen y Solis-Oba^[4]​ presentan un algoritmo FPTAS asintótico. Es un algoritmo que, para cada e > 0, completa al menos ${\displaystyle (1-\varepsilon )\cdot \mathrm {OPT} (I)-1}$ intervalos si la suma de todos los elementos es mayor que ${\displaystyle 13B/\epsilon ^{3}}$ (si la suma de los elementos es menor, entonces el óptimo es, como máximo, ${\displaystyle 13/\epsilon ^{3}\in O(1/\epsilon ^{3})}$). Se ejecuta en tiempo ${\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)}$, donde ${\displaystyle {\mathcal {T_{M}}}(n)}$ es la complejidad en tiempo de ejecución del mejor algoritmo disponible para matrices invertibles (actualmente, alrededor de ${\displaystyle O(n^{2.38})}$). Este algoritmo mejora la aproximación 3/4 incluso cuando ${\displaystyle \varepsilon <1/4}$, y en este caso las constantes son razonables (aproximadamente ${\displaystyle 2^{10}n^{2}+2^{18}}$).

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

En el problema de la asignación justa de artículos, hay diferentes personas, cada una de las cuales atribuye un valor diferente a cada elemento. El objetivo es asignar a cada persona un contenedor con una serie de elementos, de modo que el valor de cada contenedor sea al menos una constante determinada, y el mayor número posible de personas reciba un contenedor. En este problema también se utilizan muchas técnicas de reparto en contenedores.

• Python: el paquete prtpy contiene un código con los algoritmos de Csirik-Frenk-Labbe-Zhang.