How to solve variable sized bin packing when the items have equal weights, or is it still NP-hard?

Question

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?

Answer 1

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.

Answer 2

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.