How to linearise the constraint with a product term?

Question

I would like to linear the following constraint $$y\cdot \sum_{i=1}^{N}\mu_ix_i \geq M$$ where $y$ is a positive integer variable, $x_i \in \{0,1\}, i =1,...,N$ are binary variables, $\mu_i, i =1,...,N$ and $M$ are positive constants.

Thank you.

Answer 1

As long as the $x_i$ are not all zero, this inequality can always be satisfied by taking $y$ large enough. So this is equivalent to $\sum_i x_i \geq 1$.

Answer 2

If $D$ is a sufficiently large constant:

$$\begin{array}{l} \sum_i \mu_i y_i \geq M \\ 0\leq y_i \leq Dx_i \\ 0\leq y-y_i\leq D(1-x_i) \end{array} $$

Then $x_i=0$ forces $y_i=0$ and $x_i=1$ forces $y_i=y$.