¿Es NP-difícil llenar contenedores con movimientos mínimos?

33

Hay n contenedores m tipo de bolas. El i th bin tiene etiquetas ai,j para 1jm , es el número esperado de bolas de tipo j .

Comienzas con bj bolas de tipo j . Cada bola de tipo j tiene peso wj , y desea colocar las bolas en los contenedores de manera que el contenedor i tenga peso ci . Una distribución de bolas de modo que se cumpla la condición anterior se llama una solución factible.

Considere una solución factible con xi,j bolas de tipo j en el contenedor i , entonces el costo es i=1nj=1m|ai,jxi,j|. Queremos encontrar una solución factible de costo mínimo.

Este problema es claramente NP-hard si no hay restricción en {wj} . El problema de la suma de subconjuntos se reduce a la existencia de una solución factible.

Sin embargo, si agregamos la condición de que wj divide wj+1 por cada j , entonces la reducción de la suma del subconjunto ya no funciona, por lo que no está claro si el problema resultante sigue siendo NP-duro. Verificar la existencia de una solución factible solo requiere O(nm) tiempo (adjunto al final de la pregunta), pero esto no nos da la solución factible de costo mínimo.

El problema tiene una formulación de programa entero equivalente. Dado ai,j,ci,bj,wj para 1in,1jm :

Minimize:i=1nj=1m|ai,jxi,j|subject to:j=1mxi,jwj=ci for all 1ini=1nxi,jbj for all 1jmxi,j0 for all 1in,1jm

Mi pregunta es,

¿Es NP-hard el programa entero anterior cuando wj divide wj+1 para todo j ?

Un algoritmo para decidir si hay una solución factible en O(nm) tiempo:

Definir wm+1=wm(maxjcj+1) y dj=wj+1/wj . Deje que a%b sea ​​el resto cuando a se divide por b .

  1. Si existe un ci que no es divisible por w1 , devuelve "ninguna solución factible". (la invariante ci divide wj siempre se mantendrá en el siguiente ciclo)
  2. para j de 1 a m :

    1. ki=1n(ci/wj)%dj . (se requiere el mínimo de bolas de pesowj )
    2. Si bj<k , devuelve "ninguna solución factible".
    3. cici((ci/wj)%dj) para todoi . (eliminar el número mínimo de bolas de peso requeridaswj )
    4. bj+1(bjk)/dj . (agrupe las bolas más pequeñas en una bola más grande)
  3. volver "hay una solución factible".

Una solución de tiempo polinomial para el caso especial donde n=1 , y wj son potencias de 2 s

Se sabe que si n=1 y todos los wj son potencias de 2 , entonces este caso especial se puede resolver en tiempo polinómico.

Minimize:j=1m|ajxj|subject to:j=1mwjxj=c0xjbj for all 1jm

La solución fue insinuada por Yuzhou Gu , y se puede encontrar una reseña aquí .

Chao Xu
fuente

Respuestas:

0

Algunos antecedentes. El problema anterior es el problema de la mochila con restricciones. La solución más eficiente del problema de la mochila con o sin restricciones se puede resolver en tiempo pseudopolinómico, aún NP-Hard. Para algunas variaciones, vea https://en.wikipedia.org/wiki/Knapsack_problem#Definition . La primera restricción en esta variación es que el valor de los artículos (bolas) que se colocarán en la mochila (contenedores) no importa. El problema se limita a la cantidad de tiempo que lleva colocar los artículos en la mochila. El problema original requiere que los artículos más valiosos se coloquen en el menor tiempo posible. Otra restricción con esta versión es que los pesos y todos los demás argumentos son enteros. Y la restricción de interés es que los pesoswjdivide para todo j . Nota: el problema de la mochila fraccional se puede resolver en tiempo polinómico, pero no presenta las soluciones más prácticas para el problema original. Este problema utiliza números enteros que se dividen en partes iguales (sin soluciones racionales). Quizás vea ¿Cuál es el problema con el problema de la mochila? .wj+1j

La pregunta principal quizás debería ser "¿este problema sigue siendo NP-Hard cuando no está acotado por un polinomio correspondiente a i , ya que el problema es menos complejo (en P) cuando está acotado? La razón por la que digo esto es porque el problema se puede demostrar que está en P cuando w j está acotado y NP-Hard cuando w j no necesariamente divide w j + 1wjiwjwjwj+1de manera uniforme (los pesos son simplemente aleatorios), todas las restricciones limitan la complejidad de este problema a estas dos condiciones. Estas condiciones (1. el problema de la mochila de peso aleatorio sin la restricción del valor del artículo y 2. el problema de la mochila de peso divisible sin la restricción del valor del artículo) se niegan entre sí en términos de reducción de la complejidad, ya que los cocientes de los pesos pueden ser aleatorios ( especialmente cuando no está limitado), imponiendo así cálculos de tiempo exponencial (esto se mostrará en el ejemplo a continuación). Además, debido a que divide w j + 1 , w j aumenta de tamaño exponencialmente para cada jwjwj+1wjj. Esto se debe a que en lugar de usar elementos ponderados al azar (bolas cuyo peso unitario puede estar limitado a pesos unitarios por debajo de 100 o 50 o incluso 10), la restricción hace que la complejidad del tiempo dependa del número de dígitos de , lo mismo como división de prueba, que es exponencial.wj

Entonces, sí, el programa entero anterior sigue siendo NP-hard incluso cuando divide w j + 1 para todo j . wjwj+1j Y esto se observa fácilmente.

Ejemplo 1: sea y w p sean potencias de dos. Debido a la constante dos, todo el problema se resuelve en tiempo cuadrático, como muestra su ejemplo. Los pesos no son aleatorios y, por lo tanto, el cálculo se resuelve de manera eficiente.n=1wp

Ejemplo 2: dejemos que se defina como w jp , donde p es el número primo correspondiente a j , de modo que p = 2 , j = 1 : p = 3 , j = 2 , p = 5 , j = 3 , p = 7 , j = 4 , . . . , P , Jwj+1wjppjp=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,J. Esto es aplicable, ya que divide w j + 1 para todo j . Obtenemos que cada w j es el producto de todos los primos hasta j . Los valores de los pesos unitarios aumentan como tal: 1 , 2 , 6 , 30 , 210 , 2310 , 30030 , . . . . Como hay un límite ( p j ~ j l o g ( j )wjwj+1jwjj1,2,6,30,210,2310,30030,...pjjlog(j), a través del teorema del número primo), como los cocientes son todos primos, obtenemos la complejidad NP-Intermedio.

Ejemplo 3: dejemos que se defina como w jR p , donde R p es un número primo elegido al azar de dos a infinito, correspondiente a j . Esto es aplicable a este problema, ya que w j divide w j + 1 para todo j . Obtenemos los primeros 5 cocientes (cayendo aleatoriamente de dos a infinito), como 101 , 2657 , 7 , 3169 , 2wj+1wjRpRpjwjwj+1j101,2657,7,3169,2. Vemos que incluso en la quinta bola, el peso tiene once dígitos. Afortunadamente, el quinto cociente fue dos y no un primo del orden de o más. 10100

El ejemplo tres anterior es lo que sucede cuando no está limitado (pesos aleatorios) por un polinomio correspondiente a i . La complejidad del tiempo es exponencial, NP-Hard. Para cierta perspectiva, solo sume todos los pesos, vea si encajan. Pero no hay una solución para resolverlo significativamente más rápido al hacer que los pesos sean divisibles que intentar cada subconjunto para ver si funciona. Después de unas pocas docenas de bolas, aún estás entrando en el reino de incluso los billones de subconjuntos o billones de dígitos.wji

Jeff
fuente
1
But prime factorization is considered not to be NP-hard. It is considered to be NP-indermediate.
rus9384
2
I don't see a reduction here. What is the actual reduction? Taking input of prime factorization, and somehow output the factorization using solution of the integer program.
Chao Xu
2
Would do you mean by "the above integer program is NP-hard"? An individual program cannot be NP-hard.
Yuval Filmus
1
In fact prime factorization is in NPcoNP. So, it is NP-hard if NP=coNP.
rus9384
2
Unfortunately, the additional edits did not clear it up. An actual reduction would be helpful.
Chao Xu