5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – Eddie
    Nov 19 at 7:13
  • $\begingroup$ 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. $\endgroup$
    – Eddie
    Nov 25 at 6:21
  • $\begingroup$ @Eddie I updated my answer to address your latest comment. $\endgroup$
    – RobPratt
    Nov 25 at 16:54
  • $\begingroup$ Thank you again! $\endgroup$
    – Eddie
    Nov 27 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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