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

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?

• With Gurobi 9.0 you can have it automatically linearized. The theory is explained in this webinar. You can write the linearized model to a file and inspect the chosen linearization.
– ktnr
Oct 24, 2019 at 11:30
• Related (but not exactly the same since your variable is general integer while the variable in the link is continuous): or.stackexchange.com/q/39/38 Oct 24, 2019 at 13:36
• @LarrySnyder610 The answer that you link to can still be applied. It is only needed that one of the variables is binary, and the other has known bounds. Oct 24, 2019 at 14:24

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:

1. $$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.