Instancia de bin-packing no trivial con 5 objetos.

Question

El problema de empaquetamiento de contenedores es un problema en el que hay que encontrar el número mínimo de contenedores de tamaño $v$ necesario para almacenar $n$ objetos de tamaños $s_1, \ldots, s_n$ . El tamaño de los objetos nunca es superior a $v$ .

Por ejemplo, si $v = 10$ y los tamaños de los objetos son $2, 5, 4, 7, 1, 3, 8$ podemos almacenar objetos con 3 contenedores: $[8, 2], [7, 3], [5, 4, 1]$ pero no con 2 contenedores o menos, ya que esto dejaría algunos artículos sin empaquetar. Por lo tanto, 3 es el número mínimo de contenedores necesarios, y $[8, 2], [7, 3], [5, 4, 1]$ es una solución óptima.

La heurística de mejor ajuste-decrecimiento es una estrategia de empaquetamiento, cuyo objetivo es producir un empaquetamiento cercano al óptimo. Primero ordena todos los elementos en orden descendente. A continuación, recorre todos los artículos y, para cada uno de ellos, intenta encontrar un contenedor en el que quepa el artículo y cuya capacidad libre sea la más cercana al tamaño del mismo. Si existe dicha papelera, coloca el objeto en ella. Si no existe, crea una nueva papelera y lo coloca allí.

Una instancia de bin-packing no trivial es una instancia del problema que no puede ser resuelta de forma óptima por la heurística de mejor ajuste-decrecimiento.

Por ejemplo, la instancia $v = 7$ , $n=6$ donde los tamaños son $3, 2, 3, 2, 2, 2$ no es trivial, porque la heurística decreciente de mejor ajuste lo hará:

1. Clasificar los artículos para dar $3, 3, 2, 2, 2, 2$
2. Poner los dos primeros artículos en la primera papelera, produciendo una papelera $[3, 3]$
3. Poner los siguientes tres elementos en la segunda papelera, produciendo una papelera $[2, 2, 2]$
4. Poner el último artículo en la tercera papelera, produciendo un embalaje $[3, 3], [2, 2, 2], [2]$

Este es un empaquetamiento válido, pero no óptimo, ya que requiere 3 contenedores, y existe un empaquetamiento válido con dos contenedores: $[3, 2, 2], [3, 2, 2]$ .

¿Existe una instancia no trivial de empaquetamiento de contenedores con $n=5$ ?

Answer 1

No, no existe tal instancia para ningún $n\le 5$ . De hecho, suponga lo contrario. Elija el más pequeño $n$ para lo cual $O<A$ , donde $O$ es el número de recipientes en un embalaje óptimo y $A$ sea el número de recipientes en un empaquetamiento encontrado por la heurística de mejor ajuste-decrecimiento. Enumerar los objetos en un orden tal que $s_1\ge s_2\ge\dots\ge s_n$ . Ahora utilizamos las siguientes observaciones sencillas.

Si $O=1$ entonces $A=1$ .

Supongamos que en un empaquetamiento óptimo existe una papelera que contiene un solo objeto. Pero, como $s_1\le v$ Sin pérdida de generalidad, podemos suponer que el contenedor contiene el objeto 1 y los demás objetos colocados en el primer contenedor mediante la heurística de mejor ajuste. Eliminando estos objetos de la lista de objetos, reducimos el problema a un número menor de objetos, lo que contradice la minimidad de $n$ .

Las observaciones anteriores implican que $O=2$ porque, de lo contrario, ya que $n<6$ en cada empaquetamiento óptimo existe una bandeja que contiene un solo objeto. Ahora fijemos un empaquetamiento óptimo y consideremos una papelera que contenga el objeto $1$ . Si la papelera contiene al menos otros dos objetos, se puede comprobar fácilmente que $A=2$ . Si la papelera contiene como máximo otro objeto $i$ entonces la otra bandeja contiene todos los objetos restantes. Entonces, en el empaquetamiento creado por la heurística de mejor ajuste-decrecimiento, la primera bandeja contiene al menos el Objeto $1$ y Objeto $j$ con $j\le i$ por lo que la segunda papelera contiene todos los demás objetos, ya que es capaz de contenerlos, por lo que $A=2$ .

Answer 2

Definir un conjunto de objetos $x_1,x_2, ... ,x_k$ para dominar un conjunto de objetos $y_1,y_2, ... ,y_l$ si $k\ge l$ y $x_i\ge y_i$ para $1\ge i\ge l.$ Si se establece $X$ domina el conjunto $Y$ entonces la existencia de una solución con $n$ contenedores para $X$ implica una solución con $n$ contenedores para $Y$ .

Supongamos ahora que existe una solución con menos recipientes { $A_i$ } que la solución de primer ajuste y que $B_1$ sea el primer contenedor de la solución de primer ajuste. El contenido de $B_1$ no puede ser dominado por el contenido de cualquier $A_i$ por definición del algoritmo de primer ajuste. Además, el contenido de $B_1$ no puede dominar el contenido de cualquier $A_i$ ya que si lo hiciera, los objetos que quedan para el otro $B_i$ dominarían los que quedan para el otro $A_i$ ¡y tendríamos otro bin packing no trivial con menos objetos y podemos restringir este análisis a ese ejemplo más pequeño!

Dejemos que $A_1$ sea una bandeja que contenga el objeto más grande $s$ . Ahora $B_1$ debe, por supuesto, contiene $s$ y el resultado no dominante significa que $B_1$ debe contener al menos dos objetos. El resultado no dominante significa entonces que cada $A_i$ debe contener al menos tres objetos y por eso $n$ debe ser de al menos 6.