8
$\begingroup$

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?

$\endgroup$
  • 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
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.