3
$\begingroup$

For those who think visually, say I've got 5 warehouses with a current stock level of # of fish, and a target level for each. How do I achieve the new target levels in as few truck shipments as possible?

enter image description here

Or given an array A{250, 150, 45, 205, 350}, how can it be transformed to {200, 200, 150, 320, 130} in as few transfers as possible? Moving 50 from A[0] to A[1] would be an efficient first move.

I'm sure I could muddle through this and come up with something, but I'm also sure this problem has already been solved by people smarter than me. And it's important to me that it be correct and as efficient as possible. This is a little outside my normal work, and I'm not sure how to search for something like this (I couldn't find anything).

Thanks much!


Update: An initial thought ... find the warehouse with the biggest deficit, then find the one with the biggest (or closest matching?) surplus, do the shipment, then repeat. Seems like that would work, but I'm not sure if there's a more elegant or efficient solution. I'll add an answer once I've got the code working.

$\endgroup$
6
  • 1
    $\begingroup$ Can you define exactly "as few truck shipments as possible" ? Does the example " Moving 50 from A[0] to A[1]" count for one or several truck shipement ? $\endgroup$ – Optidad Oct 1 '20 at 16:08
  • $\begingroup$ That's one shipment. Another way to look at it would be money in bank accounts, and moving it in as few transfers as possible. $\endgroup$ – matt1616 Oct 1 '20 at 16:10
  • 3
    $\begingroup$ Note that your initial thought is not optimal. Just consider the case were surplus are {+9, +8} and deficit {-8, -7, -2}. Your greedy approach would solve it in 4 shipements while it can be done in only 3. $\endgroup$ – Optidad Oct 2 '20 at 8:06
  • $\begingroup$ As noted by Optidad, greedy algorithm will not work in general. $\endgroup$ – John L. Oct 2 '20 at 8:34
  • 1
    $\begingroup$ This problem has come up in a few guises, e.g. stackoverflow.com/a/20676392/47984. $\endgroup$ – j_random_hacker Oct 24 '20 at 17:44
2
$\begingroup$

There is no polynomial-time algorithm unless $\mathsf{P}=\mathsf{NP}$. Here is a proof.

Let $d_1, d_2, \cdots, d_n$ be the change for each warehouse to reach its target level. For the example in the question, they are $200-250=-50$, $\ 200-150=50$, $\ 150-45-150=105$, $\ 320-205=115$, $\ 350-130=-220$. We assume that sum of all $d_i$'s is 0; otherwise, it is not possible.


Proposition: The target levels can be reached in less than $n-1$ steps if and only if there exist some $d_i$'s but not all of them whose sum is $0$.

Proof.

  • "$\Leftarrow$". Suppose, WLOG, $d_1+d_2+\cdots+d_k=0$ for some $1\le k\lt n$. Suppose $k\ge2$. Then we can find $d_i\le0\le d_j$ for some $1\le i,j\le k$. We can transfer $\min(-d_i, d_j)$ fish from warehouse $i$ to warehouse $j$. Then either warehouse $i$ or warehouse $j$ reaches its target level. Now we can apply math induction.

  • "$\Rightarrow$". Suppose the target levels can be reached in some $k$ steps, $k\lt n-1$. At most $k+1$ warehouses are involved in those $k$ steps. The sum of changes for those warehouses must be 0. Note that $k+1<n$. $\checkmark$.


Let us consider the following warehouse-distribution problem, which is an easier version of the original warehouse-distribution problem.

Given $n$ warehouses with some fish and their target levels of fish, can we use less than $n-1$ transfers to reach their target levels?

Let us recall, as explained in the Wikipedia article subset sum problem, it is $\mathsf{NP}$-hard to decide, given a multiset of integers, whether there is a non-empty subset whose sum is zero. Given a multiset of integers $f_1, f_2, \cdots, f_n$, we can construct the following instance of warehouse-distribution problem. Let $f=\sum_{i=1}^n|f_i|$. Let $n+1$ warehouses have $g_1, g_2, \cdots, g_{n+1}$ fish respectively, where $g_1=f+f_1$, $g_2=f+f_2$, $\cdots$, $g_n=f+f_n$ and $g_{n+1}=nf-\sum_{i=1}^nf_i$. The target for each warehouse is $f$ fish. We can verify easily, thanks to the proposition above, that we can use less than $n$ transfers to reach all target levels if and only if there is a non-empty sub-multiset of all $f_i$'s whose sum is zero. Hence, the warehouse-distribution problem is at least as hard as the subset sum problem.


Since a polynomial-time algorithm is unlikely, let me give an algorithm of time-complexity about $O(n2^n)$.

  1. Compute the changes, $d_1, d_2, \cdots, d_n$.

  2. For each subset $S$ of $\{1,2,\cdots, n\}$, compute $\sigma(S)=\Sigma_{i\in S}d_i$. When $\sigma(S)=0$ and $S$ is non-empty, $S$ will be called a zero-set.

  3. For each subset $S$, let $p(S)$ be the biggest number of disjoint subsets of $S$ that are zero-sets. $p(\emptyset)=0$. For non-empty $S$, use the following recurrence relation to compute $p(S)$. A proof of the recurrence relation is given later. $$p(S) = \begin{cases} \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is not a zero-set} \\ 1 + \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is a zero-set} \\ \end{cases}$$ where $S\setminus\{a\}$ means $S$ without $a$.

  4. The answer is $n-p(\{1,2,\cdots,n\})$.


First, for any subset $S$, we have $$\max_{a\in S} p(S\setminus\{a\})\le p(S)\le 1 + \max_{a\in S} p(S\setminus\{a\}).$$

Suppose $S'$ is a subset of $S$. Since any disjoint subsets of $S'$ can be considered as disjoint subsets of $S$, we have $p(S')\le p(S)$. In particular, for any number $a\in S$, we have $p(S\setminus\{a\})\le P(S)$.
Suppose $S_1, S_2, \cdots, S_{p(S)}$ be some disjoint subsets of $S$ that are zero-sets. Let $a\in S_1$. Then $S_2, S_3, \cdots, S_{p(S)}$ are also disjoint subsets of $S\setminus\{a\}$, i.e., $P(S)=1+(P(S)-1)\le 1+ p(S\setminus\{a\})$. $\quad\checkmark$.

Now, Let me explain the recurrence relation in the step 3 above.

There are two cases.

  • $S$ is not a zero-set.

    Suppose $S_1, S_2, \cdots, S_{P(S)}$ are disjoint subsets of $S$ that are zero-sets. If the union of all these subsets is $S$, then $S$ must a zero-set as well, which is not true. So there is a number $a\in S$ that is not in any of $S_1, S_2, \cdots, S_{P(S)}$. That means all of $S_1, S_2, \cdots, S_{P(S)}$ are subsets of $S\setminus\{a\}$. That is, $P(S) \le P(S\setminus\{a\})$. So, $p(S) = \max_{a\in S} p(S\setminus\{a\}).$

  • $S$ is a zero-set.

    Let $a\in S$. Suppose we have disjoint subsets $S_1, S_2, \cdots, S_d$ of $S\setminus\{a\}$ that are zero-sets. Let $S_{d+1}$ be all the numbers in $S$ but not in any of those subsets. $S_{d+1}$ contains $a$. $S_{d+1}$ is also a zero-set since $\sigma(S_{d+1})=\sigma(S)-\sigma(S_1)-\sigma(S_2)-\cdots-\sigma(S_d)=0$. Since $S_1, S_2, \cdots, S_{d+1}$ are disjoint subsets of $S$ that are zero-sets, $p(S) \ge 1 + d$. That means, $p(S)\ge 1 + \max_{a\in S} p(S\setminus\{a\}).$ So, $p(S) = 1 + \max_{a\in S} p(S\setminus\{a\}).$ $\quad\checkmark$.

$\endgroup$
12
  • $\begingroup$ @matt1616, the math and the ideas for $p(S)$ is, in fact, quite easy once you understand it. I just tried to explain it. $\endgroup$ – John L. Oct 23 '20 at 16:15
  • $\begingroup$ I may have time to add a program in Python or Java. Or you can add one to my answer. $\endgroup$ – John L. Oct 23 '20 at 16:16
  • $\begingroup$ I'm stuck now on the computation time to figure out all possible disjoint subsets. I found this example implementation here: [stackoverflow.com/questions/30769867/… A set of 12 takes 5 seconds, and a set of 13 took an hour before I gave up on it. Any ideas on an efficient implementation of this? $\endgroup$ – matt1616 Oct 23 '20 at 22:38
  • 2
    $\begingroup$ @matt1616: The nice thing about this DP algorithm is that you don't have to enumerate all partitions :) Starting with $S$ being the complete set of warehouses, choose an arbitrary fixed warehouse $x$ to remove, and then evaluate $p(S\setminus \{x,y\})$ for each $y$ in $S\setminus\{x\}$. Accumulate all $y$ values that leave $p(S\setminus \{x,y\}) = p(S\setminus \{x\})$ into the set $T$ -- these are the elements that, together with $x$, form one of the disjoint sets in some optimal solution. Output $T$, set $S := S \setminus T$, and repeat to find the remaining disjoint sets. $\endgroup$ – j_random_hacker Oct 24 '20 at 18:34
  • 1
    $\begingroup$ @matt1616 Please take a look at my Java implementation of the algorithm. On my old laptop, 28 warehouses can be computed within 20 seconds. $\endgroup$ – John L. Oct 24 '20 at 18:57
1
$\begingroup$

This is just a rephrasing John L.'s excellent answer in layman's terms in case someone else comes to this and has trouble working through the proof like I did.

The key information we need to work with is the difference between the starting level and the finish/target level for each warehouse. d1,d2,...,dn. Also, the problem assumes that the start and finish total levels must match (ie. the sum of their differences should be zero).

k = # of steps (shipments). n = number of warehouses. For any given surplus/deficit pair (-di,dj),a shipment always results in one of them meeting their target level. So the maximum number of steps is n-1.

We only get less than n-1 steps if there are some subsets of warehouses that have perfectly matching surplus/deficits (ie. subsets of differences whose sum is zero). eg. {{8,-8},{-9,7,2}}. n = 5, but k=3.

So the best solution is the one that picks the maximum number of disjoint subsets that sum to zero (aka. zero-sets).

John defined an algorithm above and implemented it here.

The implementation begins with building the sum of the differences for all possible subsets.
And then returns the solution set with the maximum number of zero-sets.

His implementation is much more efficient than the solution that I was building upon that built every possible disjoint subset.

$\endgroup$
1
  • $\begingroup$ Nice explanation! $\endgroup$ – John L. Dec 1 '20 at 11:09

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.