3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Luis P Jun 11 '18 at 20:03
  • $\begingroup$ 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.) $\endgroup$ – D.W. Jun 11 '18 at 21:37
  • $\begingroup$ Many thanks, it's clearer now and properly reflects my problem. $\endgroup$ – Luis P Jun 11 '18 at 23:55
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Jul 12 '18 at 11:37
  • $\begingroup$ 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. $\endgroup$ – Luis P Sep 12 '18 at 12:26
  • $\begingroup$ @j_random_hacker, oops, I somehow missed your comment earlier, but I agree. I edited my answer. I don't know what I was thinking earlier. Thank you! $\endgroup$ – D.W. Sep 12 '18 at 15:19
  • $\begingroup$ @LuisP, yeah, agreed. Thanks for the comment! $\endgroup$ – D.W. Sep 12 '18 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.