5
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – prubin ♦
    Oct 22, 2022 at 21:05
  • $\begingroup$ 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 $\endgroup$
    – Vergil
    Oct 22, 2022 at 21:07
  • $\begingroup$ 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? $\endgroup$
    – fontanf
    Oct 24, 2022 at 10:33
  • $\begingroup$ @fontanf Yes. That's correct! $\endgroup$
    – Vergil
    Oct 24, 2022 at 15:33
  • $\begingroup$ 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" $\endgroup$
    – fontanf
    Oct 24, 2022 at 21:11

1 Answer 1

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Vergil
    Oct 23, 2022 at 0:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.