# Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity

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.

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