I have $m$ items and $n$ bins where each item $i$ and bin $j$ has a value $v_{i,j}$. Each bin $j$ has a value $V_j$. I want to pack the items into the bins such that

(1) I minimize the ratio of the values of packed items to the number of packed items while using all bins;

(2) an item can be packed into only one bin; and

(3) The values of the item packed into bin $j$ is at least $V_j$.

If $S_j$ are the items packed in bin $j$, then I want to maximize $\sum_j\sum_{i\in S_j}v_{i,j}/\sum_j|S_j|$ such that $\sum_{i\in S_j}v_{i,j}\ge V_j$.

I have been looking for this problem on the internet and I found that it is very similar to the GAP problem or the Min-GAP problem (https://epubs.siam.org/doi/abs/10.1137/S0097539700382820?journalCode=smjcat or http://www.or.deis.unibo.it/kp/Chapter7.pdf) but I am not sure if it is equivalent to one of them. In GAP, we are maximizing the profit while guaranteeing the capacity of each bin. In Min-GAP, we are minimizing the cost while also guaranteeing the capacity of each bin.

In my problem, I have no limit on the capacity of each bin. Even if I want only to minimize $\sum_{j}|S_j|$ or maximize $\sum_j\sum_{i\in S_j}v_{i,j}$, the problem seems different than GAP or Min-GAP.

If you see any obvious reduction, can you describe how to reduce my problem (or the linear variants I described above) to GAP or Min-GAP so that I can efficiently solve my problem.

  • 1
    $\begingroup$ Checking whether there is an assignment satisfying constraints (2) and (3) together is already NP-Complete. $\endgroup$ Dec 5, 2023 at 0:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.