É NP-difícil encher caixas com movimentos mínimos?

33

Existem n caixas e m tipo de bolas. O i th bin tem rótulos ai,j para 1jm , que é o número esperado de bolas do tipo j .

Você começa com bj bolas do tipo j . Cada esfera de tipo j tem peso wj , e deseja colocar as bolas dentro dos recipientes de tal modo que bin i tem peso ci . Uma distribuição de bolas de tal forma que a condição anterior se mantém é chamada de solução viável.

Considere uma solução viável com xi,j bolas do tipo j na posição i , então o custo é i=1nj=1m|ai,jxi,j|. Queremos encontrar uma solução viável de custo mínimo.

Esse problema é claramente difícil para NP se não houver restrição em {wj} . O problema da soma do subconjunto reduz-se à existência de uma solução viável.

No entanto, se adicionarmos a condição que wj divide wj+1 para cada j , a redução da soma do subconjunto não funcionará mais, portanto, não está claro se o problema resultante permanece NP-difícil. A verificação da existência de uma solução viável leva apenas O(nm) tempo (anexado ao final da pergunta), mas isso não nos fornece a solução viável de custo mínimo.

O problema tem uma formulação de programa inteiro 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

Minha pergunta é,

O programa inteiro acima é NP-hard quando wj divide wj+1 para todos os j ?

Um algoritmo para decidir se existe uma solução viável em O(nm) tempo:

Definir wm+1=wm(maxjcj+1) e dj=wj+1/wj . Seja a%b o remanescente quando a for dividido por b .

  1. Se existir um ci que não seja divisível por w1 , retorne "nenhuma solução viável". (o invariante ci divide wj irá sempre ser mantida no ciclo seguinte)
  2. para j de 1 a m :

    1. ki=1n(ci/wj)%dj . (o mínimo de bolas de pesowj necessário)
    2. Se bj<k , retorne "nenhuma solução viável".
    3. cici((ci/wj)%dj) para todosi . (remova o número mínimo de bolas necessárias de pesowj )
    4. bj+1(bjk)/dj . (agrupe bolas menores em uma bola maior)
  3. retornar "existe uma solução viável".

Uma solução de tempo polinomial para o caso especial em que n=1 , e wj são potência de 2 s

Sabe-se que se n=1 e todos os wj são potências de 2 , esse caso especial pode ser resolvido em tempo polinomial.

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

A solução foi sugerida por Yuzhou Gu , e uma redação pode ser encontrada aqui .

Chao Xu
fonte

Respostas:

0

Algum plano de fundo. O problema acima é o problema da mochila com restrições. A solução de problema de mochila mais eficiente, com ou sem restrições, pode ser resolvida em tempo pseudopolinomial, ainda NP-Hard. Para algumas variações, consulte https://en.wikipedia.org/wiki/Knapsack_problem#Definition . A primeira restrição nessa variação é que o valor dos itens (bolas) a serem colocados na mochila (caixas) não importa. O problema é restrito à quantidade de tempo que leva para colocar os itens na mochila. O problema original requer que os itens mais valiosos sejam colocados no menor tempo possível. Outra restrição com esta versão é que os pesos e todos os outros argumentos são inteiros. E a restrição de interesse é que os pesoswjdivida para todos os j . Nota: o problema da mochila fracionária pode ser resolvido em tempo polinomial, mas não apresenta as soluções mais práticas para o problema original. Esse problema usa números inteiros que se dividem igualmente (sem soluções racionais). Talvez veja Qual é o grande problema com o problema da mochila? .wj+1j

A principal pergunta talvez deve ser "é este problema ainda NP-Hard quando é ilimitado por um polinômio correspondente ao i , como o problema é menos complexa (em P) quando é limitado? A razão de eu dizer isso é porque o problema pode ser mostrado em P quando w j é delimitado e NP-Hard quando w j não necessariamente divide w j + 1wjiwjwjwj+1uniformemente (os pesos são simplesmente aleatórios), todas as restrições limitam a complexidade desse problema a essas duas condições. Essas condições (1. o problema da mochila de peso aleatório sem a restrição de valor do item e 2. o problema da mochila de peso divisível sem a restrição de valor do item) se negam em termos de redução da complexidade, pois os quocientes dos pesos podem ser aleatórios ( especialmente quando ilimitado), impondo cálculos de tempo exponencial (isso será mostrado no exemplo abaixo). Além disso, como divide w j + 1 , w j aumenta exponencialmente em tamanho para cada jwjwj+1wjj. Isso ocorre porque, em vez de usar itens ponderados aleatórios (bolas cujo peso unitário pode ser limitado a pesos unitários inferiores a 100 ou 50 ou mesmo 10), a restrição faz com que a complexidade do tempo dependa do número de dígitos de , o mesmo como divisão de teste, que é exponencial.wj

Portanto, sim, o programa inteiro acima permanece NP-difícil, mesmo quando divide w j + 1 para todos os j . wjwj+1j E isso é facilmente observado.

Exemplo 1: Seja e w p sejam potências de dois. Por causa da constante dois, todo o problema é resolvido no tempo quadrático, como mostra o seu exemplo. Os pesos não são aleatórios e, portanto, o cálculo é resolvido com eficiência.n=1wp

wj+1wjppjp=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,Jwjwj+1jwjj1,2,6,30,210,2310,30030,...pj ~ jlog(j), via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

Example 3: let wj+1 be defined as wjRp, where Rp is a randomly chosen prime number from two to infinity, corresponding to j. This is applicable to this problem, as wj divides wj+1 for all j. We get the first 5 quotients (randomly falling from two to infinity), as 101,2657,7,3169,2. We see that even at the 5th ball, the weight has eleven digits. Fortunately, the fifth quotient was two and not a prime in the order of 10100 or larger.

Example three above is what happens when wj is not bounded (random weights) by a polynomial corresponding to i. The time complexity is exponential, NP-Hard. For some perspective, just add up all the weights, see if they fit. But there isn’t a solution to solving it significantly faster by making the weights divisible than trying each subset to see if it works. After a few dozen balls, you are still entering the realm of even the trillions of subsets or trillions of digits.

Jeff
fonte
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