0
$\begingroup$

Consider the variable sized bin packing

$$ \begin{align*}\tag{P1a}\label{P1a} & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}} & & \sum_{j=1}^nf_jy_j\\[3pt] & \text{subject to} & & \sum_{i=1}^{m} w_{i}x_{ij} \leqslant C_{j}y_j,\forall\,j\in\{1,\dots,n\}\tag{P1b}\label{P1b}\\[3pt] & & & \sum_{j=1}^n x_{ij}=1, \forall\, i \in\{1,\dots,m\}\tag{P1c}\\[3pt] & & & x_{ij}, y_j \in\{0, 1\}, \forall\, i\in\{1,\dots,m\}, j\in\{1,\dots,n\}\tag{P1d}. \end{align*} $$

The problem \eqref{P1a} can be found for example in variable sized bin packing problem.

The problem \eqref{P1a} can be seen as:

  • We have set of bins $\{1,\dots,n\}$ each with a weight $f_j$, a set of items $\{1,\dots,m\}$ each with a weight $w_i$. For each bin $j$, there is a capacity $C_{j}$.
  • We would like to assign all items to the bins such that every item is assigned to exactly one bin and the weights of items assigned to bin $j$ does not exceed the capacity $C_{j}$.

I am curious about the case where the weights of the items are all equal, say $w_i=1$ for all $i$. Can we derive an optimal algorithm in this case or it is still NP-hard?

I can't find an NP-hardness reduction but I think that we can do this algorithm:

  • sort the bins by $C_j$ in decreasing order;
  • start with bin 1, fill it with items until $C_1$ is reached;
  • go to the next bin and loop.

I have tried this algorithm with few examples but I cannot prove its optimality though.

Could you help please?

$\endgroup$
  • $\begingroup$ Easy counterexample: $C_1=101, C_2=100, f_1=50, f_2=1$. Sorting the bins in increasing order of $f_j$ instead is susceptible to a similar counterexample. $\endgroup$ – j_random_hacker Jan 21 '17 at 17:23
  • $\begingroup$ Yes right, if I sort them with $C_j/f_j$ instead? $\endgroup$ – Ribz Jan 21 '17 at 17:26
  • $\begingroup$ That's a better heuristic than sorting by $C_j$ or $f_j$ alone, but it can still fail: $C_1=1, C_2=2, f_1=2, f_2=5, m=2, x_i=1$. The resulting solution uses both bins, even though only the second (more-expensive on a per-unit basis) is needed. $\endgroup$ – j_random_hacker Jan 21 '17 at 17:35
  • $\begingroup$ So, it is more probably that the problem still NP-hard even with all $w_i=1$? $\endgroup$ – Ribz Jan 21 '17 at 17:43
3
$\begingroup$

I'll change the description to avoid artificial sums.

We have n bins $bin_i$. Each bin has a capacity $C_i$ and a weight $f_i$. We have m items $item_i$. Each item has a weight $w_j$. We want to pick a set B of bins, and for each $bin_i$ in B a set $I_i$ such that the weights of all items in $I_i$ is at most $C_i$, and the sum of the weights $f_i$ of the bins in B is minimised. Each item must be in exactly one of the bins $bin_i$ in B. We assume $f_i > 0$ and $w_i > 0$.

If all $w_i = w$ are the same, then we can divide each $C_i$ by w and replace $w_i$ by 1 without changing the problem. Now the number of items in $I_i$ must be ≤ $C_i$. Since the number of items in $I_i$ is an integer, we can round each $C_i$ down to the nearest integer without changing the problem.

There are m items, and each item is exactly in one bin, so the sum of the $C_i$ for bins $bin_i$ in B is ≥ m for a solution. On the other hand, if the sum of $C_i$ for bins in B is ≥ m, then we can fit the m items into those bins (because the $C_i$ are integers). So now we can completely ignore the items, and the problem is: Find a set B of bins so that the sum of $C_i$ for bins in B is ≥ m, while the sum of $f_i$ for those bins is minimised. If we find the set B, then putting items into the bins is trivial.

Let B' be the set of bins not in B, and let C be the sum of all $C_i$. Instead of finding B, we can find B' such that the sum of $C_i$ for bins in B' is ≤ C - m, and the sum of $f_i$ for bins in B' is maximised. We rename "bin" to "item" and call B' a "knapsack", and voila - a knapsack problem. Very much easier to solve than the original problem if the number of bins is significantly smaller than the number of items, but still NP-complete.

$\endgroup$
1
$\begingroup$

I would first simplify the problem: If the $w_i$ are equal, you can assume that all the $c_{ij}$ are integers. It then doesn't matter item you put into every bin, just how many. So you pick $y_i = 0$ or $y_i = 1$, such that the sum of $C_i y_i ≥ n$ and the sum of $f_i y_i$ is minimal.

Looks very similar to the knapsack problem to me. Actually, instead of trying to find the bins that you are using, you could find the bins that you are not using, and then it is exactly the knapsack problem (which is NP-complete).

Your algorithm cannot be optimal because you want to minimize the sum of $f_i y_i$ but the algorithm doesn't even consider the $f_i$ at all.

$\endgroup$
  • $\begingroup$ Thank you. But if the input $C_j$ are not integers? And, why do you have the sum of $C_jy_j$ greater than $n$? It must be greater than the number of items in bin $j$ instead, right? $\endgroup$ – Ribz Jan 21 '17 at 17:21
  • $\begingroup$ Because each of the n items must be put into some bin, so the total number of items in bins must be ≥ n. You can put Ci items in a bin, therefore the sum of Ci yi must be ≥ n - you must pick bins with a total capacity ≥ n. $\endgroup$ – gnasher729 Jan 21 '17 at 20:27
  • $\begingroup$ If the Cj are not integers - say C5 = 4.9. So you can fit 4.9 items into that bin. Since you must put whole items you can fit 4 items into that bin, so assume C5 = 4 and not 4.9. $\endgroup$ – gnasher729 Jan 21 '17 at 20:28
  • $\begingroup$ The number of items is $m$ and not $n$. We must put these items into the minimum possible number of bins (assume $f_j=1$) such that the number of items in bin $j$ does not exceed its capacity $C_j$. $\endgroup$ – Ribz Jan 21 '17 at 20:36
  • $\begingroup$ Another point: how to transform it to a knapsack problem while there are multiple bins? $\endgroup$ – Ribz Jan 21 '17 at 20:56

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.