# 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 '19 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 – LarrySnyder610 Oct 24 '19 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. – Kevin Dalmeijer Oct 24 '19 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.