Linearizing this absolute difference objective function $\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$

Question

For $x_i>0, i=1,\ldots,I$, I tried to linearize this objective function $$\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$$ as $$\min\sum_{i=1}^{I}\sum_{j=1}^{i}y_{ij}$$ subject to \begin{align} & y_{ij} \le x_i-x_j \quad i=1,\ldots,I, j =1,\ldots,i\\ & y_{ij} \le x_j-x_i \quad i=1,\ldots,I, j =1,\ldots,i\\ & y_{ij} \ge x_i-x_j + M(1-z_{ij}) \quad i=1,\ldots,I, j =1,\ldots,i\\ & y_{ij} \ge x_j-x_i + Mz_{ij} \quad i=,\ldots,I, j =1,\ldots,i \end{align} and $z_{ij}\in\{0,1\}, \forall i=1,\ldots,I, j =1,\ldots,i$.

Is this linearization correct? Is there a way to avoid $M$-constraints to avoid computational problems?

Answer 1

As you are minimizing $y_{ij}$, it is sufficient to use $$ y_{ij} \geq x_i - x_j \quad \forall i, j \\ y_{ij} \geq x_j - x_i \quad \forall i, j $$