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