2
$\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$
10
$\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$
4
  • $\begingroup$ Dear Rob, may check with you if my reasoning is correct since the x variables have already been defined to be binary, through the first inequality of your reply, it is inconsequential even if z has been relaxed as x will force it to be either 1 or 0. Through relaxing it does it help to boost solution speed? Thank you. $\endgroup$ – Mike May 11 at 11:53
  • 1
    $\begingroup$ 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. $\endgroup$ – RobPratt May 11 at 12:32
  • $\begingroup$ Thank you, Rob! $\endgroup$ – Mike May 11 at 13:56
  • 1
    $\begingroup$ 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. $\endgroup$ – RobPratt May 26 at 12:40

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.