# Which linearisation technique is correct?

I have the objective function (Maximally Diverse Grouping Problem) as

$$\max\sum_{g=1}^G\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}d_{ij}x_{ig}x_{jg}$$

Here, $$d_{ij}$$ are known parameters, and $$x_{ig}$$ and $$x_{jg}$$ are binary variables.

It is nonlinear as we have the bilinear term, $$x_{ig}x_{jg}$$.

### Linearization Technique 1

We can linearise it by introducing an binary variable $$z_{ijg}=x_{ig}x_{jg}$$

\begin{align}z_{ijg} &\le x_{ig}\\z_{ijg} &\le x_{jg}\\z_{ijg}&\ge x_{ig}+x_{jg}-1\end{align}

Now, the new objection function becomes

$$\max\sum_{g=1}^G\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}d_{ij}z_{ijg}$$

### Linearization Technique 2

I do not introduce any extra variables. Instead I rewrite the objective function as

$$\max\sum_{g=1}^G\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}d_{ij}(x_{ig}+x_{jg}-1)$$

They are equivalent except when $$x_{i,g}=x_{j,g}=0$$, in which case the second linearization incorrectly contributes $$-d_{ij}$$ to the objective.
Assuming $$d_{ij} \ge 0$$, I recommend a third linearization (relaxing $$z$$ and omitting two constraints from linearization 1): \begin{align} z_{ijg}&\ge x_{ig}+x_{jg}-1 \\ z_{ijg}&\ge 0 \end{align}
• Yes, if $d>0$ and $x$ is declared binary, $z$ will automatically be binary-valued even if you relax to $z \ge 0$. Relaxing $z$ might or might not speed things up, but that is the motivation. A best practice is to try it both ways on realistic instances. May 11 at 12:32
• I see now that you have changed the objective sense from minimization to maximization, and that invalidates my answer. For maximization, you should instead keep the other two ($\le$) constraints. May 26 at 12:40