[Solved]: Bin packing problem or not?

Problem Detail: 

Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items):

Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to maximize the number of items in the bins subject to:

• One bin contains at most one item.
• If item $i$ is on bin $j$ then $g_{ij}\geq1$ must hold now if all other bins are empty.
• If item $i$ is on bin $j$ (so $g_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$, then $g_{ij}\geq g_{ij^\prime}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}$ must both hold now.
• If item $i$ is on bin $j$ (so $g_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$ (so $g_{ij}\geq g_{ij^\prime}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}$ must both hold now) and item $i^{\prime\prime}$ is on bin $j^{\prime\prime}$, then $g_{ij}\geq g_{ij^\prime}+g_{ij^{\prime\prime}}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}+g_{i^\prime j^{\prime\prime}}$ and $g_{i^{\prime\prime} j^{\prime\prime}}\geq g_{i^{\prime\prime} j}+g_{i^{\prime\prime} j^{\prime}}$ must all hold now.
• And so on and so forth.
• In general I will have the following constraint: $g_{ij}x_{ij}\geq\sum\limits_{i^\prime=1,\;i^\prime \neq i}^{M}\sum\limits_{j^\prime=1,\;j^\prime \neq j}^{N}g_{ij^\prime}x_{i^\prime j^\prime}$, where $x_{ij}$ equals $1$ if item $i$ is in bin $j$ and equals $0$ otherwise.

Finally, I have the following problem:

Maximize $\sum\limits_{i=1}^{M}\sum\limits_{j=1}^{N}x_{ij}$

subject to

• $\frac{g_{ij}x_{ij}}{\sum\limits_{i^\prime=1,\;i^\prime \neq i}^{M}\sum\limits_{j^\prime=1,\;j^\prime \neq j}^{N}g_{ij^\prime}x_{i^\prime j^\prime}}\geq x_{ij},\; \forall i, j,$ (C1)

• $\sum\limits_{j=1}^{N}x_{ij}\leq1,\; \forall i,$ (C2)

• $\sum\limits_{i=1}^{M}x_{ij}\leq1,\; \forall j,$ (C3)

and $x_{ij}\in\{0, 1\},\; \forall i, j,$ (C4)

The input of the problem is $M$, $N$, and $g_{ij},\;\forall i,j$. The right hand side of constraint (C1) is to say that when item $i$ is not in bin $j$ (i.e., $x_{ij}=0$) then (C1) is not violated. (C2) and (C3) say that one item goes to one bin and one bin contains one item, respectively. Finally, (C4) is the variable of the problem which is a binary variable.

My question is: Can I say that this problem is a bin packing problem and it is therefore NP-hard? If not, Can you suggest a reduction idea from an NP-complete problem?

Thank you for your help.

Asked By : npisinp

Answered By : FrankW

You can't simply say: "This is a bin packing problem and therefore NP-hard."
Consider the problem of $N$ unit bins and $M$ unit items with the target of maximizing the usage of the bins. Clearly this is also a bin packing problem, but it is not NP-hard.

However, you can reduce to the decision variant of your problem from partition:

Given a set of items with sizes $a_1, \dotsc, a_k$, can it be partitioned into two subsets of equal size.

Given items $a_1, \dotsc, a_k$, we construct an instance of your problem as follows:

• Let $A_i = \sum_{j=1}^i a_j$ amd $A=A_k$.
• We introduce $2A+2$ items and $2A+2$ bins.
• $g_{i,j} = \begin{cases} A-a_l & A_{l-1}<i=j\leq A_l\\ A-a_l & A+A_{l-1}<i=j\leq A+A_l\\ 0 & A_{l-1}<i,j\leq A_l,~ i\neq j\\ 0 & A+A_{l-1}<i,j\leq A+A_l,~ i\neq j\\ 2 & A_{l-1}<i\leq A_l,~ A+A_{l-1}<j\leq A+A_l\\ 2 & A+A_{l-1}<i\leq A+A_l,~ A_{l-1}<j\leq A_l\\ 0 & j>2A,~ i\neq j\\ \frac A2 & i=j>2A\\ 0 & i=2A+1,~ j\leq A\\ 0 & i=2A+2,~ A<j\leq 2A\\ 1 & \text{otherwise} \end{cases}$
• We ask for an assignment with $\sum_{i=1}^{A}\sum_{j=1}^{A} x_{i,j} \geq A+2$.

The construction works as follows:

• Any solution will satisfy $x_{i,j}=1 \Rightarrow i=j$.
• Items/bins $i$ with $A_{l-1} < i \leq A_l$ resp. $A+A_{l-1} < i \leq A+A_l$ correspond to $a_l$. In a solution, exactly one of the groups will be taken, corresponding to $a_l$ being in the first resp. second set of the partition.
• The threshold can only be reached, if the last two items are placed, ensuring that the partition is into two sets of size $\frac A2$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22136

3.2K people like this

 Download Related Notes/Documents