Est-il difficile de remplir les bacs avec un minimum de mouvements?

33

Il y a nn bacs et mm type de balles. La ii ième bin a des étiquettes a i , jai,j pour 1 j m1jm , c'est le nombre attendu de billes de type jj .

Vous commencez avec b jbj boules de type jj . Chaque boule de type jj a un poids w jwj et veut placer les boules dans les bacs de telle sorte que la bin ii ait un poids c ici . Une distribution de billes telle que la condition précédente est maintenue est appelée une solution réalisable.

Considérons une solution réalisable avec x i , jxi,j boules de type jj dans le bac ii , le coût est Σ n i = 1 Σ m j = 1 | un i , j - x i , j | ni=1mj=1|ai,jxi,j|. Nous voulons trouver une solution réalisable au moindre coût.

Ce problème est clairement NP-difficile s'il n'y a pas de restriction sur { w j }{wj} . Le problème de la somme des sous-ensembles se réduit à l’existence d’une solution réalisable.

However, if we add the condition that wjwj divides wj+1wj+1 for every jj, then the subset sum reduction no longer works, so it's not clear whether the resulting problem remains NP-hard. Checking for the existence of a feasible solution takes only O(nm)O(nm) time (attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has an equivalent integer program formulation. Given ai,j,ci,bj,wjai,j,ci,bj,wj for 1in,1jm1in,1jm: Minimize:ni=1mj=1|ai,jxi,j|subject to:mj=1xi,jwj=ci for all 1inni=1xi,jbj for all 1jmxi,j0 for all 1in,1jm

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

My question is,

Is the above integer program NP-hard when wjwj divides wj+1wj+1 for all jj?

An algorithm to decide if there is a feasible solution in O(nm)O(nm) time:

Define wm+1=wm(maxjcj+1)wm+1=wm(maxjcj+1) and dj=wj+1/wjdj=wj+1/wj. Let a%ba%b be the remainer when aa is divided by bb.

  1. If there exists a cici that's not divisible by w1w1, return "no feasible solution". (the invariant cici divides wjwj will always be maintained in the following loop)
  2. for jj from 11 to mm:

    1. kni=1(ci/wj)%djkni=1(ci/wj)%dj. (the minimum of balls of weight wjwj required)
    2. If bj<kbj<k, return "no feasible solution".
    3. cici((ci/wj)%dj)cici((ci/wj)%dj) for all ii. (remove the minimum number of required balls of weight wjwj)
    4. bj+1(bjk)/djbj+1(bjk)/dj. (group smaller balls into a larger ball)
  3. return "there is a feasible solution".

A polynomial time solution to the special case where n=1n=1, and wjwj are power of 22s

It is known that if n=1n=1 and all wjwj are powers of 22, then this special case can be solved in polynomial time. Minimize:mj=1|ajxj|subject to:mj=1wjxj=c0xjbj for all 1jm

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

The solution was hinted at by Yuzhou Gu, and a write up may be found here.

Chao Xu
la source

Réponses:

0

Some background. The above problem is the knapsack problem with restrictions. The most efficient knapsack problem solution with or without restrictions can be solved in pseudopolynomial time, still NP-Hard. For some variations, see https://en.wikipedia.org/wiki/Knapsack_problem#Definition. The first restriction in this variation is that the value of items (balls) to be placed in the knapsack (bins) does not matter. The problem is then restricted to the amount of time it takes to put the items in the knapsack. The original problem requires the most valuable items to be placed in as short amount of time possible. Another restriction with this version is that the weights and all other arguments are integers. And the restriction of interest is that the weights wjwj divide wj+1wj+1 for all jj. Note: the fractional knapsack problem can be solved in polynomial time, but does not present the most practical solutions to the original problem. This problem uses integers that divide evenly (no rational solutions). Perhaps see What's the big deal with the knapsack problem?.

The main question perhaps should be "is this problem still NP-Hard when wjwj is unbounded by a polynomial corresponding to ii, as the problem is less complex (in P) when it is bounded? The reason I say this is because the problem can be shown to be in P when wjwj is bounded and NP-Hard when wjwj does not necessarily divide wj+1wj+1 evenly (the weights are simply random), all restrictions limit the complexity of this problem to these two conditions. These conditions (1. the random weight knapsack problem without the item-value restriction and 2. divisible weight knapsack problem without the item-value restriction) negate each other in terms of reducing complexity, as the quotients of the weights may be random themselves (especially when unbounded), thus imposing exponential time calculations (this will be shown in the example below). Additionally, because wjwj divides wj+1wj+1, wjwj increases in size exponentially for each jj. This is because instead of using random weighted items (balls whose unit weight may all be limited to unit weights under 100 or 50 or even 10), the restriction instead causes the time complexity to depend on the number of digits of wjwj, the same as trial division, which is exponential.

So yes, the above integer program remains NP-hard even when wjwj divides wj+1wj+1 for all jj. And this is easily observed.

Example 1: let n=1n=1 and wpwp be powers of two. Because of constant two, the entire problem is solved in quadratic time, as your example shows. The weights are not random and therefore the calculation is solved efficiently.

Example 2: let wj+1wj+1 be defined as wjpwjp, where pp is the prime number corresponding to jj, such that p=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,Jp=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,J. This is applicable, as wjwj divides wj+1wj+1 for all jj. We get each wjwj is the product of all the primes up to jj. The values of the unit weights increase as such: 1,2,6,30,210,2310,30030,.... Since there is a bound (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
la source
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