# Bin packing with twin items

Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no bin exceeds its capacity. In this standard from, the bin packing problem is well known to be NP-hard. However, consider a version of the problem where every items has a twin of equal size. More formally, if $i$ and $j$ are twins, it holds that $x_i = x_j$.

For two bins, the problem is easy since there exists a feasible solution if and only if a packing where no twins share the same bin is feasible. However, what happens if we have more than two bins? I suspect that the problem becomes NP-hard. Unfortunately, I have not been able to prove this so far.

Does anyone have an idea for a reduction or know if the problem has been studied before? Also, if the problem is hard for twins, does the hardness carry over to triplets, quadruplets etc.?

• One obvious approach is: Given a instance of bin packing, create an instance of twinned bin packing by cloning (twinning) all the items and cloning (twinning) all of the bins. However, this doesn't work. If there's a solution to the original bin packing problem, there'll be a solution to the derived twinned bin packing problem... but the converse doesn't hold. Just documenting something that doesn't work.
– D.W.
Aug 25, 2015 at 16:43
• @D.W. you are correct. Although I found it somewhat tricky to find an example, where the normal bin packing instance has no solution but the twin version does. Take for instance 6 bins of capacity 27 and 18 items with sizes 1, 1, 1, 3, 3, 5, 7, 7, 9, 9, 9, 9, 9, 13, 13, 19, 21, 23. It is easy to verify that there is no feasible packing. However, if we have twice the number of bins and every item has a twin, then there is a feasible solution, namely [23, 3, 1], [23, 3, 1], [21, 3, 3], [21, 5, 1], [19, 7, 1], [19, 7, 1], [13, 13, 1], [13, 7, 7], [13, 9, 5], [9, 9, 9], [9, 9, 9], [9, 9, 9]. Aug 26, 2015 at 13:38