Let's assume I have multiple tools $T=\{t_1,\dots,t_n\}$ (binary decision variables) and each tool has an efficiency, $E=\{e_1,\dots,e_n\}$. For a given $k$ I now want to maximize the efficiency:
$$\max \sum e_i t_i$$ $$\text{s.t. } \sum t_i \leq k$$
The solution would indicate which tools to choose (yes, in this very simple example a greedy algorithm (take the $k$ most efficient tools) would also do the trick ;-))
But now let's say, the tools also have an associated category $C=\{c_1,\dots,c_n\}, c_i\in\mathbb{N}$ and it is required that at least two (or more generally: $m\leq n$) tool categories are present in a feasible solution. Is there any way to encode this in a linear constraint?
Note that this is not a "no two pairs are equal" question as a certain category can occur multiple times as long as at least $m=2$ categories are covered.
Best Answer
Add a new variable $\rho_i \in [0,1]$ per category, together with the constraints $$\rho_i \le \sum_{j : c_j = i} t_i$$ and $$ \sum_i \rho_i \ge m.$$
Then, $\rho_i$ can only be $1$, if there is at least one tool from this category. Hence, the second constraint requires that we have $m$ different categories.