3
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ What's the context where you ran into this? Why do you want to know whether it is NP-complete? Is this something that came up in practice? Are you looking for a practical solution that's as good as you can do in practice? $\endgroup$ – D.W. Feb 28 '14 at 20:52
  • $\begingroup$ Thanks for your comment. It is some problem related often to wireless networks. In wireless networks every transmitting node causes interference to all other nodes in the network. I want to prove that it is an NP-hard problem. Do you see some relation to bin packing problem or to knapsack problems? $\endgroup$ – npisinp Feb 28 '14 at 22:34
  • $\begingroup$ 1) Your generalized condition does not include the requirements of one item per bin and for the case of only one $x_{i,j}$ being 1. 2) Neither version includes a requirement that an object goes into at most one bin. Is this not required? 3) Are the values $g_{i,j}$ given as part of the input? (I assume as much, since otherwise the problem would be trivial.) $\endgroup$ – FrankW Feb 28 '14 at 23:54
  • $\begingroup$ I don't understand the optimization problem. What is given as input, and what are the variables that are free to vary? Are you told which items are in which bins, and the $g_{i,j}$'s are the unknowns? Are we given the $g_{i,j}$'s and have to find a placement of items into bins that is consistent with all of your constraints? Are of the $g_{i,j}$'s required/guaranteed to be $\ge 0$? Can you edit the question to clarify these questions and FrankW's questions? $\endgroup$ – D.W. Mar 1 '14 at 4:55
  • $\begingroup$ Again, thank you for your comments. You are right I did not write it very clear. The input is the weights $g_{ij}$, $M$, and $N$. I modified the problem accordingly. $\endgroup$ – npisinp Mar 1 '14 at 16:18
9
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Thank you again for your help. Very smart thoughts and idea. Only I did not get your 4th bullet. Is the sum goes to $2A+2$ instead of $A$? $\endgroup$ – npisinp Mar 1 '14 at 17:26
  • $\begingroup$ No, the sum only goes to $A+2$: $\frac A2$ of the first $A$ items, $\frac A2$ of the next $A$ and the final $2$. $\endgroup$ – FrankW Mar 1 '14 at 18:21
  • $\begingroup$ Can the $g_{ij}$ overlap with each other? For example, we can find $g_{44}=0$ for the first case and $g_{44}=-1$ for the second case. Which one to choose? I took the following instance of partition problem: $a_1=1, a_2=2, a_3=1$. $\endgroup$ – npisinp Mar 1 '14 at 20:28
  • 1
    $\begingroup$ The cases for $g_{i,j}$ do not overlap. Also they do not get negative. For your example we get $A_1=1$, $A_2=3$, $A=A_3=4$ and $A_0=0$. So $g_{4,4}$ is defined by the first case as $4-a_3 = 3$. $\endgroup$ – FrankW Mar 1 '14 at 20:51
  • $\begingroup$ If I take the following example: $a_1=1$ and $a_2=1$. The solution to this partition problem is clearly the two sets $\{1\}$ and $\{1\}$. Following your reduction. I will have $A_1=1$, $A=A_2=2$. I have $6$ items and $6$ bins. And I will assign $x_{11}=1$, $x_{22}=1$, $x_{33}=1$, and $x_{44}=1$ but I cannot satisfy the constraints, i.e., $g_{11}<g_{12}+g_{13}+g_{14}$ which violates the constraints. So, how the equivalence is shown? Partition $\Leftrightarrow$ My problem $\endgroup$ – npisinp Mar 3 '14 at 19:57

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.