I would like to add a new constraint to a standard Knapsack problem by introducing groups. My variables are $x_c \in \mathbb{Z}^+, c\in \mathbb{C}$. Where $\mathbb{C}$ is the set of all items. Each item belongs to a specific group $g_i, i\in \mathbb{G}$ and these groups are mutually exclusive.
I would like to optimize with limiting the number of groups my items belong to. (let's say $k$ groups)
Is it still possible to formulate this as a MIP problem and how?
For $i\in \mathbb{G}$, let binary variable $y_i$ indicate whether some item from group $i$ is selected. Let $\overline{x}_c$ be an upper bound on $x_c$, which you can obtain from the knapsack constraint. Impose the following linear constraints: \begin{align} x_c &\le \overline{x}_c y_i &&\text{for $i\in \mathbb{G}$ and $c \in g_i$}\\ \sum_{i\in G} y_i &\le k \end{align} The first constraint enforces $x_c > 0 \implies y_i=1$. The second constraint limits the number of selected groups to $k$.