0
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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}

$\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.