# Identifying the variant of such a knapsack-like problem

I am not too familiar with variants of knapsack problems (or variants of possibly other classical OR problems), but I would like to identify the following Integer Programming problem: $$\min_{x_i,y_{i,j}} \sum_i c_i x_i$$

subject to $$\sum_i y_{i,j} \le s_j \ \forall j$$ $$\sum_i u_{i,j} y_{i,j} \ge v \ \forall j$$ $$y_{i,j} \le x_i \ \forall j$$ $$x_i,y_{i,j} \in \{0,1\}.$$

Does this integer program belong to some sorts of variants of famous problems?

• Welcome to OR SE. Should $u_{i,l}$ in your second constraint be $u_{i,j},$ and is $u$ a parameter (constant) versus a variable?
– prubin
Commented Oct 22, 2022 at 21:05
• Thanks for the reply! My bad, it should be $u_{i,j}$. And yes, $u$ is a parameter. Only $x_i$ and $y_{i,j}$ are variables. @prubin Commented Oct 22, 2022 at 21:07
• You can use multiple copies of an item, for example, $y_{i,0} = 1$, $y_{i,1} = 1$, but you cannot assign multiple copies to the same knapsack, since $y_{i,j}$ is binary. Is that right? Commented Oct 24, 2022 at 10:33
• @fontanf Yes. That's correct! Commented Oct 24, 2022 at 15:33
• Then I'm not aware of such problem in the literature (that doesn't mean there aren't). You have a cardinality constraint, there are a couple of papers about the "knapsack problem with cardinality constraint". And the objective can be interpreted as setup costs, and there are a couple of papers about the "knapsack problem with setups" Commented Oct 24, 2022 at 21:11

Looks like a variant of the minimum-weight multiset multicover problem with the additional restriction that the required copies of item $$j$$ must be coverable by at most $$s_j$$ chosen multisets $$i$$. What is the source of your problem?

• It's my ongoing research project. You can think of $u_{i,j}$ as the utility of item $i$ to customer $j$, $x_{i}$ as the availability of item $i$, $y_{i,j}$ as the consumption of item $i$ by customer $j$, and $v$ is a certain utility threshold. Commented Oct 23, 2022 at 0:19