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

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?

• I will formalise the problem statement, but in the meantime the answers are: all items must be transferred, $n$ is not fixed and is part of the solution. Actually, the solution is the set of moves (source_bin, n, target_bin) that minimizes its cardinality. – Luis P Jun 11 '18 at 20:03
• Thanks for the explanation. I edited your question based on my understanding; please check that it correctly reflects your problem. (Note that requests for software recommendations are off-topic here.) – D.W. Jun 11 '18 at 21:37
• Many thanks, it's clearer now and properly reflects my problem. – Luis P Jun 11 '18 at 23:55

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.
• Don't you need exactly 2 target bins? If you have $n$, it seems that you could just move every source bin to a "corresponding" output bin in a single move, regardless of whether there is a solution to the partition problem. – j_random_hacker Jul 12 '18 at 11:37
• I think @j_random_hacker is right. To reduce to the partition problem we should have two subsets with equal sum. So the explanation stands with $2$ target bins. – Luis P Sep 12 '18 at 12:26