Is it NP-hard to fill up bins with minimum moves?

Question

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.

You start with $b_j$ balls of type $j$. Each ball of type $j$ has weight $w_j$, and want to put the balls into the bins such that bin $i$ has weight $c_i$. A distribution of balls such that previous condition holds is called a feasible solution.

Consider a feasible solution with $x_{i,j}$ balls of type $j$ in bin $i$, then the cost is $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. We want to find a minimum cost feasible solution.

This problem is clearly NP-hard if there is no restriction on $\{w_j\}$. The subset sum problem reduces to the existence of a feasible solution.

However, if we add the condition that $w_j$ divides $w_{j+1}$ for every $j$, 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(n\,m)$ 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 $a_{i,j},c_i,b_j,w_j$ for $1\leq i\leq n,1\leq j\leq m$: \begin{align*} \text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\ \text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\ & \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\ & x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\ \end{align*}

My question is,

Is the above integer program NP-hard when $w_j$ divides $w_{j+1}$ for all $j$?

An algorithm to decide if there is a feasible solution in $O(n\,m)$ time:

Define $w_{m+1}=w_m(\max_{j} c_j + 1)$ and $d_j = w_{j+1}/w_j$. Let $a\%b$ be the remainer when $a$ is divided by $b$.

1. If there exists a $c_i$ that's not divisible by $w_1$, return "no feasible solution". (the invariant $c_i$ divides $w_j$ will always be maintained in the following loop)

2. for $j$ from $1$ to $m$:

   1. $k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$. (the minimum of balls of weight $w_j$ required)
   2. If $b_j<k$, return "no feasible solution".
   3. $c_i \gets c_i - ((c_i/w_j)\% d_j)$ for all $i$. (remove the minimum number of required balls of weight $w_j$)
   4. $b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$. (group smaller balls into a larger ball)
3. return "there is a feasible solution".

A polynomial time solution to the special case where $n=1$, and $w_j$ are power of $2$s

It is known that if $n=1$ and all $w_j$ are powers of $2$, then this special case can be solved in polynomial time. \begin{align*} \text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\ \text{subject to:} & \sum_{j=1}^m w_j x_j = c\\ & 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\ \end{align*}

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

Answer 1

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 $w_j$ divide $w_{j+1}$ for all $j$. 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 $w_j$ is unbounded by a polynomial corresponding to $i$, 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 $w_j$ is bounded and NP-Hard when $w_j$ does not necessarily divide $w_{j+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 $w_j$ divides $w_{j+1}$, $w_j$ increases in size exponentially for each $j$. 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 $w_j$, the same as trial division, which is exponential.

So yes, the above integer program remains NP-hard even when $w_j$ divides $w_{j+1}$ for all $j$. And this is easily observed.

Example 1: let $n = 1$ and $w_p$ 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 $w_{j+1}$ be defined as $w_j * p$, where $p$ is the prime number corresponding to $j$, such that $p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$. This is applicable, as $w_j$ divides $w_{j+1}$ for all $j$. We get each $w_j$ is the product of all the primes up to $j$. The values of the unit weights increase as such: $1, 2, 6, 30, 210, 2310, 30030, ...$. Since there is a bound ($p_j$ ~ $j log (j)$, via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

Example 3: let $w_{j+1}$ be defined as $w_j * R_p$, where $R_p$ is a randomly chosen prime number from two to infinity, corresponding to $j$. This is applicable to this problem, as $w_j$ divides $w_{j+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 $10^{100}$ or larger.

Example three above is what happens when $w_j$ 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.