# Linearizing objective function with absolute differences

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.

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$$.
• 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$? – RobPratt Jan 29 at 18:37