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?

  • 1
    $\begingroup$ 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. $\endgroup$ – ktnr Oct 24 '19 at 11:30
  • 5
    $\begingroup$ 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 $\endgroup$ – LarrySnyder610 Oct 24 '19 at 13:36
  • 4
    $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

