Linearizing nested absolute values

In [1] an interesting question is posted: How to model a nested absolute value: $$\min \left| \left( |x_1-a_1| \right) - \left( |x_2-a_2|\right) \right|$$ A standard way to model absolute values in the objective function in a linear minimization model $$\min |x|$$ is: $$\begin{align}\min\>&y\\&-y \le x \le y\end{align}$$ It would be tempting to apply this here: $$\begin{align}\min\>&z\\&-z\le y_1-y_2 \le z\\& -y_i \le x_i - a_i \le y_i \end{align}$$ The easiest way to illustrate this formulation is wrong, is showing a counter example. For this I added a few extra conditions to the model: $$\begin{align}\min\>&z\\&-z\le y_1-y_2 \le z\\& -y_i \le x_i - a_i \le y_i\\&x_1=x_2\\&x_1,x_2 \in [2,5] \end{align}$$ When using $a_1 = -1$, $a_2=2$, I see as solution:

----     37 PARAMETER a  

i1 -1.000,    i2  2.000


----     37 VARIABLE x.L  

i1 2.000,    i2 2.000


----     37 VARIABLE y.L  

i1 3.000,    i2 3.000


----     37 VARIABLE z.L                   =        0.000  

We can see the value  $y_2=3$ is incorrect: $|x_2-a_2|=|2-2|=0$. The underlying reason is of course: we are not minimizing the second term $|y_2-a_2|$.

A correct formulation will need extra binary variables (or something related such as a SOS1 construct): $$\begin{align}\min\>&z\\&-z\le y_1-y_2 \le z\\& y_i \ge x_i - a_i \\& y_i \ge -(x_i - a_i)\\ & y_i \le x_i - a_i + M\delta_i\\& y_i \le -(x_i - a_i) + M(1-\delta_i)\\&\delta_i \in \{0,1\}  \end{align}$$

Background

The function $z = \max(x,y)$ can be linearized as: $$\begin{align}&z \ge x\\&z \ge y\\ &z \le x + M\delta\\&z \le y + M(1-\delta)\\&\delta \in \{0,1\}\end{align}$$ The function $z=|x|$ can be interpreted as $z=\max(x,-x)$.

Results

The example model now will show:

----     68 VARIABLE x.L  

i1 2.000,    i2 2.000


----     68 VARIABLE y.L  

i1 3.000


----     68 VARIABLE z.L                   =        3.000  

----     68 VARIABLE d.L  

                      ( ALL       0.000 )

I think we need binary variables for for both terms $y_i$ although for this numerical example it seems that we could only do it for the second term $y_2$, and handle $y_1$ as before, I believe that is just luck. A correct formulation will use binary variables for both inner absolute values.

Linearizing absolute values is not always that easy.

References

1. Linear Programming: Converting nested absolute value, https://math.stackexchange.com/questions/2625516/linear-programming-converting-nested-absolute-value