Minimum number of moves required to transfer items from source bins to target bins?

Question

I have a set of source bins, each with some number of items, and a set of target bins. I want to move all of the items from the source bins to the target bins, using the minimum number of moves. Each move can move any number of items from one source bin to one target bin.

The bins do not have the same size, but the total capacity of source and target bins is the same.

I came up with a few possible formulations for this problem:

1) as a problem of finding the sparsest solution to an underdetermined system of linear equations with variables in $\mathbf N_0$. Lots of literature about this but very sparse (no pun intended) on $\mathbf N$.

2) I could also describe it as finding the min cost flow of a bi-partite network $G=\{U,V,E\}$, fully connected, with $U$ supply nodes (source bins) and $V$ demand nodes (target bins) with $|U|$ not necessarily equal to $|V|$, edge cost given by

$$c_{uv} = \begin{cases} 1 &\text{if link is used}\\ 0 &\text{otherwise} \end{cases}$$

and the total demand equal to the total supply.

However, the cost is non-linear so usual min cost flow algorithms do not work here.

3) and I also considered the Split Deliveries Vehicle Routing problem with vehicles (source bins), vehicle capacity (size of source bins) customer demand as the target bins, and a space where all inter customer location distances are 1.

All of these are NP-Hard problems.

My questions:

What is the complexity of this problem? Can it be solved in polynomial time? Is there any research literature covering this problem?

Answer 1

The problem is NP-hard, by reduction from the partition problem.

Here is the reduction. Consider an instance of the partition problem, namely, integer $x_1,\dots,x_n$. Create $n$ source bins and 2 target bins, with $x_i$ items in the $i$th source bin. Set the capacity on the target bins to $(x_1+\dots+x_n)/2$. Then there is a solution to your movement problem that uses exactly $n$ moves, if and only if there is a solution to the partition problem.

We can also show your problem is strongly NP-hard, by reduction from 3-partition.

As a result, you should not expect to find any efficient algorithm that always gives the optimal answer and scales to large problems. You might try looking for heuristics, approximation algorithms, or algorithms that could be exponential time in the worst case but hopefully are often fast in practice. For instance, you could look into simulated annealing, integer linear programming, and approximation algorithms for bin packing.