6

I am trying to create an LP problem which is like the knapsack problem but with groups of items. Let's say there are 10 groups of items each with up to 5 items. Each group has one special item and you must choose only one, let's call that group the "special group". There's a bonus of 4 if you take 1 more item from the special group and a bonus of 8 if you pick two.

What I have tried is having g[1:10] which identifies the special group, then a[5row, 10col] which tells me how many items were taken from each group, then a new variable b[1:5] (max # of items). I then tried this constraint: [i=1:5], b[i] <= sum(g[j] * a[i,j] for j in 1:10). My goal here was that since I only care about my special group, I would multiply each group's item count in a by whether it's the special group in g. This introduces a quadratic constraint which is not allowed in my solver.

What is the right approach to this problem?

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Eddie
  • 197
  • 4

1 Answers1

8

If I understand correctly, binary variable $g_j$ indicates whether group $j$ is special, binary variable $a_{i,j}$ indicates whether exactly $i$ items are taken from group $j$, and binary variable $b_i$ indicates whether exactly $i$ items are taken from the special group. You want to enforce the logical implication $$b_i \implies \bigvee_j (g_j \land a_{i,j})$$ One approach is to introduce a new binary variable $c_{i,j}$ and enforce \begin{align} c_{i,j} &\implies (g_j \land a_{i,j}) \tag1 \\ b_i &\implies \bigvee_j c_{i,j} \tag2 \end{align} Rewriting $(1)$ in conjunctive normal form yields $$ c_{i,j} \implies (g_j \land a_{i,j}) \\ \lnot c_{i,j} \lor (g_j \land a_{i,j}) \\ (\lnot c_{i,j} \lor g_j) \land (\lnot c_{i,j} \lor a_{i,j}) \\ (1 - c_{i,j} + g_j \ge 1) \land (1 - c_{i,j} + a_{i,j} \ge 1) \\ (c_{i,j} \le g_j) \land (c_{i,j} \le a_{i,j}) $$ Rewriting $(2)$ in conjunctive normal form yields $$ b_i \implies \bigvee_j c_{i,j} \\ \lnot b_i \lor \bigvee_j c_{i,j} \\ 1 - b_i + \sum_j c_{i,j} \ge 1 \\ b_i \le \sum_j c_{i,j} $$ So the desired linear constraints are \begin{align} c_{i,j} &\le g_j \\ c_{i,j} &\le a_{i,j} \\ b_i &\le \sum_j c_{i,j} \end{align}


From your comment, it sounds like you also want to enforce the converse of $(1)$: $$(g_j \land a_{i,j}) \implies c_{i,j}$$ One approach is to again use conjunctive normal form to obtain $$g_j + a_{i,j} - 1 \le c_{i,j} \quad \text{for all $i$ and $j$} $$ But because there is only one count per group, you have $\sum_i a_{i,j}=1$ and can instead use "compact linearization" to obtain fewer constraints. Explicitly, summing both sides of $$c_{i,j} = g_j a_{i,j}$$ over $i$ yields $$\sum_i c_{i,j} = g_j \tag3$$ Because there is only one special group, you have $\sum_j g_j=1$ and can further sum over $j$ to obtain just one constraint: $$\sum_{i,j} c_{i,j} = 1 \tag4$$ as you suggested. Constraint $(3)$ yields a tighter LP formulation because constraint $(4)$ is an aggregation, but either one is sufficient to enforce your desired behavior.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Thank you so much for the detailed annotation. It's not something I'm too familiar and this is so incredibly helpful. This solved it! Thank you again! – Eddie Nov 19 '21 at 07:13
  • should there be another constraint that the sum of c == 1? If g[j] and a[i,j] are both 1, c[i,j] being 0 would satisfy these constraints. I am seeing some instances in my code where this is happening, so just wanted to double check if I missed something. – Eddie Nov 25 '21 at 06:21
  • @Eddie I updated my answer to address your latest comment. – RobPratt Nov 25 '21 at 16:54
  • Thank you again! – Eddie Nov 27 '21 at 04:57