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

#### References

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

## No comments:

## Post a Comment