Which linearisation technique is correct?

Question

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)$$

Answer 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}