0
$\begingroup$

I'm trying to figure out what this NP-hard problem is most similar to and therefore which solutions are available to me.

There are a fixed number k of bins, each with the same initial capacity c1. There are a number of items of different sizes packed into each of the bins, such that the sum of the sizes of the items in each bin is less than c1. In other words, we are given a viable solution to the bin packing problem.

If we now change the capacity of each of the bins to c2 < c1, can we redistribute the items so that the sum of the sizes of the items in each bin is now less than c2, in such a way that minimises the total amount of size moved. There is no limit on the number of items in each bin, just the sum of their sizes.

Illustrated as an example:

c1 = 20

|     |    |     |    |     |    |  4  |
|  3  |    |  2  |    |  1  |    |  2  |
|  1  |    |  1  |    |  7  |    |  3  |
|  4  |    |  7  |    |  4  |    |  4  |
|__3__|    |__4__|    |__4__|    |__5__|

First bin total = 11 < 20
Second bin total = 14 < 20
Third bin total = 16 < 20
Fourth bin total = 18 < 20

By changing c2 to 16, a (potentially sub-obtimal) solution is:

|  4  |    |  1  |    |     |    |     |
|  3  |    |  2  |    |     |    |  2  |
|  1  |    |  1  |    |  7  |    |  3  |
|  4  |    |  7  |    |  4  |    |  4  |
|__3__|    |__4__|    |__4__|    |__5__|

First bin total = 15 < 16
Second bin total = 15 < 16
Third bin total = 15 < 16
Fourth bin total = 14 < 16

We moved a 4 from the fourth bin to the first, and a 1 from the third bin to the second - giving a total movement of 5.

There are some similarities with a view problems I'm aware of, but nothing which quite is the same.

Formally, as a decision problem:

Given a capacity $C$, and a set of $B$ bins $\{b_1, b_2, ..., b_B\}$ each containing a number of items with varying sizes. Can we redistribute the items such that $\sum$ (contents of bin) $< C$ for each bin $\in \{b_1, b_2, ..., b_B\}$ where the total size moved is at most $M$.

$\endgroup$
  • $\begingroup$ Can you formulate this as a decision problem? It's not clear what happens if the items cannot be redistributed at all. Depending on the answer, you could reduce SUBSET-SUM to your problem. $\endgroup$ – Yuval Filmus Mar 31 '17 at 13:49
  • $\begingroup$ Given a capacity $C$, and a set of $B$ bins $\{b_1, b_2, ..., b_B\}$ each containing a number of items with varying sizes. Can we redistribute the items such that $\sum$ (contents of bin) $< C$ for each bin $\in \{b_1, b_2, ..., b_B\}$ and the total amount of size moved is at most $M$. $\endgroup$ – Matt Lane Mar 31 '17 at 15:44
  • $\begingroup$ You can reduce PARTITION to this problem. $\endgroup$ – Yuval Filmus Mar 31 '17 at 18:29
  • $\begingroup$ You first have to solve the problem whether fitting all items into k bins of size c2 is possible at all, and that would already be NP-complete (if you turn this into a decision problem where the limit for amount moved is very large). $\endgroup$ – gnasher729 Mar 31 '17 at 21:53

Your Answer

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

Browse other questions tagged or ask your own question.