I want to turn this objective function

$$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$

where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector with $n$ variables like $[x_{11} \ x_{12}]$.

Is there a way to turn this objective function into a linear form?
And how can I do that?
My problem is that I don't quite fully understand it when I have to maximize the objective function.


1 Answer 1


Introduce a new variable $z_{i,j}$ to represent the summand, and apply the linearization of $\max$ described here. Explicitly, the problem is to maximize $\sum_{i=1}^{N-1} \sum_{j=i+1}^N z_{i,j}$ subject to \begin{align} z_{i,j} &\ge T X_i^T-T X_j^T\\ z_{i,j} &\ge -T X_i^T+T X_j^T\\ z_{i,j} &\le T X_i^T-T X_j^T + M_{i,j}^1 (1-y_{i,j})\\ z_{i,j} &\le -T X_i^T+T X_j^T+ M_{i,j}^2 y_{i,j}\\ y_{i,j} &\in \{0,1\} \end{align} Here, $M_{i,j}^1$ is a small upper bound on $z_{i,j} - T X_i^T + T X_j^T$, and $M_{i,j}^2$ is a small upper bound on $z_{i,j} + T X_i^T - T X_j^T$.

The idea is that $y_{i,j}=1$ forces $z_{i,j} = T X_i^T-T X_j^T$, and $y_{i,j}=0$ forces $z_{i,j} = -T X_i^T+T X_j^T$.

  • $\begingroup$ thanks a lot, is there a way to decide how high i can set M^1 and M^2? $\endgroup$
    – T K.
    Jan 29, 2020 at 8:55
  • $\begingroup$ You should set those big-M values as small as possible, based on $T$ and bounds on $X$, without cutting off useful solutions. Do you have bounds on $X$? $\endgroup$
    – RobPratt
    Jan 29, 2020 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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