LISTA DE PROBLEMAS

El problema de 3 particiones es un problema de NP completo en informática . El problema es decidir si un conjunto múltiple de enteros dado se puede dividir en triples que tienen la misma suma. Más precisamente, dado un conjunto múltiple S de n = 3  m enteros positivos, ¿se puede dividir S en m tripletes S ₁ , S ₂ , ..., S _{m de} modo que la suma de los números en cada subconjunto sea igual? Los subconjuntos S ₁ , S ₂ , ..., S_m debe formar una partición de S en el sentido de que son disjuntos y cubren S . Let B denota el (deseada) suma de cada subconjunto S _i , o equivalentemente, deja que la suma total de los números en S sea m  B . El problema de 3 particiones sigue siendo NP-completo cuando cada número entero en S está estrictamente entre B / 4 y B / 2.

El problema de 3 particiones es similar al problema de la partición , que a su vez está relacionado con el problema de la suma de subconjuntos . En el problema de la partición, el objetivo es dividir S en dos subconjuntos con la misma suma. En 3 particiones, el objetivo es dividir S en m subconjuntos (o n / 3 subconjuntos), no solo dos subconjuntos, con la misma suma.

Ejemplo [ editar ]

El conjunto {20, 23, 25, 49, 45, 27, 40, 22, 19} se puede dividir en los tres conjuntos {20, 25, 45}, {23, 27, 40}, {49, 22, 19 } cada uno de los cuales suma 90.

Fuerte NP-completitud [ editar ]

El problema de 3 particiones sigue siendo NP completo incluso cuando los enteros en S están delimitados anteriormente por un polinomio en n . En otras palabras, el problema sigue siendo NP completo incluso cuando se representan los números en la instancia de entrada en unario. es decir, la 3-partición es NP-completa en el sentido fuerte o fuertemente NP-completa . Esta propiedad, y 3 particiones en general, es útil en muchas reducciones donde los números se representan naturalmente en unario. En contraste, se sabe que el problema de partición es NP-completo solo cuando los números están codificados en un sistema no unario y tienen un valor exponencial en n .

Descripciones [ editar ]

Garey y Johnson (1975) originalmente demostraron que la partición tridimensional era NP completa, mediante una reducción de la coincidencia tridimensional . La referencia clásica de Garey y Johnson (1979) describe una prueba de integridad de NP, reduciendo la correspondencia tridimensional a 4 particiones a 3 particiones. El problema de 4 particiones es un análogo de 3 particiones en el que el objetivo es dividir un conjunto S dado en cuádruples, todos con la misma suma: precisamente, la diferencia es que S ahora consiste en n = 4  m enteros, cada uno estrictamente entre B / 5 y B / 3.

En el problema del embalaje de los contenedores , los artículos de diferentes volúmenes deben empacarse en un número finito de contenedores o contenedores, cada uno de un volumen fijo determinado, de manera que se minimice el número de contenedores utilizados. En la teoría de la complejidad computacional , es un problema combinatorio NP-hard . ^[1] El problema de decisión (decidir si los artículos encajarán en un número específico de contenedores) es NP-completo . ^[2]

Existen muchas variaciones de este problema, como el empaque 2D, el empaque lineal, el empaque por peso, el empaque por costo, etc. Tienen muchas aplicaciones, como llenar contenedores, cargar camiones con limitaciones de capacidad de peso, crear copias de seguridad de archivos en medios y mapeo de tecnología en diseño de chip de semiconductor de matriz de puerta programable en campo .

El problema del embalaje del depósito también puede verse como un caso especial del problema del material de corte . Cuando el número de contenedores se limita a 1 y cada elemento se caracteriza por un volumen y un valor, el problema de maximizar el valor de los elementos que pueden caber en el contenedor se conoce como el problema de la mochila .

A pesar del hecho de que el problema de empaquetamiento del contenedor tiene una complejidad computacional NP-difícil , se pueden producir soluciones óptimas para casos muy grandes del problema con algoritmos sofisticados. Además, se han desarrollado muchas heurísticas : por ejemplo, el algoritmo de primer ajuste proporciona una solución rápida pero a menudo no óptima, que implica colocar cada elemento en el primer contenedor en el que encajará. Requiere tiempo Θ ( n  log  n ), donde n es el número de artículos que se deben empacar. El algoritmo se puede hacer mucho más efectivo al ordenar primerola 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 pedido de artículos que permite que el primer ajuste produzca una solución óptima. ^[3]

Una variante del embalaje de contenedores que ocurre en la práctica es cuando los artículos pueden compartir espacio cuando se empaquetan en un contenedor. Específicamente, un conjunto de artículos podría ocupar menos espacio cuando se empacan juntos que la suma de sus tamaños individuales. Esta variante se conoce como empaque VM ^[4] ya que cuando las máquinas virtuales (VM) se empaquetan en un servidor, su requisito de memoria total podría disminuir debido a las páginascompartido por las máquinas virtuales que solo necesitan almacenarse una vez. Si los artículos pueden compartir espacio de manera arbitraria, el problema del embalaje del contenedor es difícil de aproximar. Sin embargo, si el espacio compartido se ajusta a una jerarquía, como es el caso con el uso compartido de memoria en máquinas virtuales, el problema de empaquetado de contenedores puede ser aproximado de manera eficiente. Otra variante del embalaje de contenedores de interés en la práctica es el denominado embalaje de contenedores en línea . Aquí se supone que los artículos de diferente volumen llegan secuencialmente y el tomador de decisiones tiene que decidir si selecciona y empaca el artículo actualmente observado, o si no lo deja pasar. Cada decisión es sin recuerdo.

Declaración formal [ editar ]

Dado un conjunto de contenedores $${\ displaystyle S_ {1}, S_ {2} ...} con el mismo tamaño $${\ displaystyle V} y una lista de $${\ displaystyle n} artículos con tallas $${\ displaystyle a_ {1}, \, \ dots, \, a_ {n}} para empacar, encuentre un número entero de contenedores $${\ displaystyle B} y un $${\ displaystyle B}- partición $${\ displaystyle S_ {1} \ cup \ cdots \ cup S_ {B}} del conjunto $${\ displaystyle \ {1, \, \ dots, \, n \}} tal que $${\ displaystyle \ sum _ {i \ en S_ {k}} a_ {i} \ leq V} para todos $${\ displaystyle k = 1, \, \ dots, \, B.}Una solución es óptima si tiene un mínimo$${\ displaystyle B}. los$${\ displaystyle B}-valor para una solución óptima se denota OPT a continuación. Una posible formulación de problema de programación lineal entera es:

minimizar $${\ displaystyle B = \ sum _ {i = 1} ^ {n} y_ {i}}
sujeto a	$${\ displaystyle B \ geq 1,}
	$${\ displaystyle \ sum _ {j = 1} ^ {n} a_ {j} x_ {ij} \ leq Vy_ {i},}	$${\ displaystyle \ forall i \ in \ {1, \ ldots, n \}}
	$${\ displaystyle \ sum _ {i = 1} ^ {n} x_ {ij} = 1,}	$${\ displaystyle \ forall j \ in \ {1, \ ldots, n \}}
	$${\ displaystyle y_ {i} \ in \ {0,1 \},}	$${\ displaystyle \ forall i \ in \ {1, \ ldots, n \}}
	$${\ displaystyle x_ {ij} \ in \ {0,1 \},}	$${\ displaystyle \ forall i \ in \ {1, \ ldots, n \} \, \ forall j \ in \ {1, \ ldots, n \}}

dónde $${\ displaystyle y_ {i} = 1} si bin $${\ displaystyle i} se usa y $${\ displaystyle x_ {ij} = 1} si artículo $${\ displaystyle j} se pone en la papelera $${\ displaystyle i}. ^[5]

Algoritmo de primer ajuste [ editar ]

Este es un algoritmo de aproximación codicioso directo . El algoritmo procesa los elementos en orden arbitrario. Para cada artículo, intenta colocar el artículo en el primer contenedor que puede acomodar el artículo. Si no se encuentra ningún contenedor, abre un nuevo contenedor y coloca el elemento dentro del nuevo contenedor.

Este algoritmo logra un factor de aproximación de 2; El número de contenedores utilizados por este algoritmo no es más del doble del número óptimo de contenedores. En otras palabras, es imposible que 2 compartimientos estén como máximo medio llenos porque tal posibilidad implica que en algún momento, exactamente un contenedor estaba como máximo medio lleno y se abrió uno nuevo para acomodar un artículo de tamaño como máximo V / 2) Pero dado que el primero tiene al menos un espacio de V  / 2, el algoritmo no abrirá un nuevo contenedor para ningún artículo cuyo tamaño sea como máximo V  / 2. Solo después de que el contenedor se llene con más de V  / 2 o si un artículo con un tamaño mayor que V  / 2, el algoritmo puede abrir un nuevo contenedor.

Por lo tanto, si tenemos contenedores B , al menos los  contenedores B - 1 están más de la mitad llenos. Por lo tanto,{\ displaystyle \ sum _ {i = 1} ^ {n} a_ {i}> {\ tfrac {B-1} {2}} V}. Porque$${\ displaystyle {\ tfrac {\ sum _ {i = 1} ^ {n} a_ {i}} {V}}}es un límite inferior del valor óptimo OPT , obtenemos que B  - 1 <2 font="" nbsp="">OPT y, por lo tanto, B  ≤ 2 OPT . ^[6] Consulte el análisis a continuación para obtener mejores resultados de aproximación.

La disminución del primer ajuste modificado (MFFD) ^[7] mejora el FFD para artículos de más de medio contenedor clasificando los artículos por tamaño en cuatro clases de tamaño: grande, mediano, pequeño y pequeño, correspondientes a artículos con tamaño> 1/2 contenedor,> 1/3 bin,> 1/6 bin y artículos más pequeños respectivamente. Luego procede a través de cinco fases:

1. Asigne un contenedor para cada artículo grande, ordenado de mayor a menor.
2. Avanza por los contenedores. En cada uno: si el elemento medio restante más pequeño no cabe, omita este contenedor. De lo contrario, coloque el elemento mediano restante más grande que quepa.
3. Continúe hacia atrás a través de los contenedores que no contienen un elemento mediano. En cada uno: si los dos artículos pequeños restantes más pequeños no encajan, omita este contenedor. De lo contrario, coloque el artículo pequeño restante más pequeño y el artículo pequeño restante más grande que quepa.
4. Avance por todos los contenedores. Si el elemento restante más pequeño de cualquier clase de tamaño no cabe, omita este contenedor. De lo contrario, coloque el artículo más grande que quepa y permanezca en este contenedor.
5. Use FFD para empacar los elementos restantes en nuevos contenedores.

Análisis de algoritmos aproximados [ editar ]

Las estrategias de disminución del mejor ajuste y de disminución del primer ajuste se encuentran entre los algoritmos heurísticos más simples para resolver el problema del embalaje del contenedor. Se ha demostrado que no usan más de 11/9  OPT  + 1 bins (donde OPT es el número de bins dados por la solución óptima). ^[8] La más simple de ellas, la estrategia de Disminución del primer ajuste (FFD), opera ordenando primero los elementos que se insertarán en orden decreciente por su tamaño, y luego insertando cada elemento en el primer contenedor de la lista con suficiente espacio restante. A veces, sin embargo, uno no tiene la opción de ordenar la entrada, por ejemplo, cuando se enfrenta a un en líneaProblema de embalaje del contenedor. En 2007, se demostró que el límite 11/9  OPT  + 6/9 para FFD es ajustado . ^[9] MFFD utiliza no más de 71/60  OPT  + 1 bins ^[10] (es decir, limitado por aproximadamente 1.18  OPT , en comparación con aproximadamente 1.22  OPT para FFD). En 2013, Dósa y Sgall dieron un límite superior ajustado para la estrategia de primer ajuste (FF), lo que demuestra que nunca necesita más de 17/10  OPT bins para cualquier entrada. ^[11]

Algoritmo exacto [ editar ]

Martello y Toth ^[12] desarrollaron un algoritmo exacto para el problema del empaquetado bin 1-D, llamado MTP. Una alternativa más rápida es el algoritmo Bin Completion propuesto por Korf en 2002 ^[13] y luego mejorado. ^[14]

Schreiber y Korf presentaron una mejora adicional en 2013. ^[15] Se muestra que el nuevo algoritmo de Compleción de bin mejorado es hasta cinco órdenes de magnitud más rápido que la Compleción de bin en problemas no triviales con 100 elementos, y supera al BCP (rama -y-cut-and-price) algoritmo de Belov y Scheithauer sobre problemas que tienen menos de 20 contenedores como la solución óptima. El algoritmo que funcione mejor depende de las propiedades del problema, como el número de elementos, el número óptimo de contenedores, el espacio no utilizado en la solución óptima y la precisión del valor.