Bin packing problem or not?

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 n

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}2A,~ i\neq j\\
\frac A2 & i=j>2A\\
0 & i=2A+1,~ j\leq A\\
0 & i=2A+2,~ A

• 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}

• 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$.

StackExchange Computer Science Q#22136, answer score: 9