How to linearize the multiplication of an integer and a binary integer variable?

Question

I have the following constraints

\begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align} where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable and $M,S$ are known numbers.

How can I linearize this?

Answer 1

Case 1: As @KevinDalmeijer commented: If $\ \forall x_i \ \ \exists \ \ U_i \in \mathbb{Z}^+$(given upper bounds for variable $x_i$) you can define new integer variables $y_i = x_it_i \ \ \forall i \in \{1,2,...,N\}$ and then replace your constraints with the followings:

1. $\sum\limits_{1}^{N} y_i = M$
2. $t_i \leq y_i$
3. $y_i \leq t_i \times U_i$

Note that, when $t_i=0$ constraints 2 and 3 forces $y_i=0$, but when $t_i=1$, $1 \leq y_i \leq U_i$ which excludes the $x_i=0$, but as $0$ is neutral element for addition, it won't affect your summation.

Case 2: If there are no upper bounds for $x_i$ in the model, you can define constraint 3 as follow:

3. $y_i \leq t_i \times M$

which indicates that if $t_i \neq 0$, for any $i$, $y_i$ can not be greater than $M$ which is necessary to hold your first constraint.