## Monday, January 29, 2018

### 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.