- 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^{primeprime}$ is on bin $j^{primeprime}$, then $g_{ij}geq g_{ij^prime}+g_{ij^{primeprime}}$ and $g_{i^prime j^prime}geq g_{i^prime j}+g_{i^prime j^{primeprime}}$ and $g_{i^{primeprime} j^{primeprime}}geq g_{i^{primeprime} j}+g_{i^{primeprime} j^{prime}}$ must all hold now.
- And so on and so forth.
- In general I will have the following constraint: $g_{ij}x_{ij}geqsumlimits_{i^prime=1,;i^prime neq i}^{M}sumlimits_{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 $sumlimits_{i=1}^{M}sumlimits_{j=1}^{N}x_{ij}$ subject to
- $frac{g_{ij}x_{ij}}{sumlimits_{i^prime=1,;i^prime neq i}^{M}sumlimits_{j^prime=1,;j^prime neq j}^{N}g_{ij^prime}x_{i^prime j^prime}}geq x_{ij},; forall i, j,$ (C1)
- $sumlimits_{j=1}^{N}x_{ij}leq1,; forall i,$ (C2)
- $sumlimits_{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
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=jleq A_l A-a_l & A+A_{l-1}<i=jleq A+A_l 0 & A_{l-1}<i,jleq A_l,~ ineq j 0 & A+A_{l-1}<i,jleq A+A_l,~ ineq j 2 & A_{l-1}<ileq A_l,~ A+A_{l-1}<jleq A+A_l 2 & A+A_{l-1}<ileq A+A_l,~ A_{l-1}<jleq A_l 0 & j>2A,~ ineq j frac A2 & i=j>2A 0 & i=2A+1,~ jleq A 0 & i=2A+2,~ A<jleq 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
