5

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?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Vergil
  • 51
  • 3
  • 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 Oct 22 '22 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 – Vergil Oct 22 '22 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? – fontanf Oct 24 '22 at 10:33
  • @fontanf Yes. That's correct! – Vergil Oct 24 '22 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" – fontanf Oct 24 '22 at 21:11

1 Answers1

3

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?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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. – Vergil Oct 23 '22 at 00:19