# Optimize for bonuses within a group (knapsack)

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?

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.