Linear program with absolute values in the objective I know that if there is a absolute values in Linear Programming problem, i.e.

$min \sum_{i} c_i|x_i|$ s.t $Ax \leq b, x \geq 0$ >

then, I can change $|x_i|$ into new variables such as $|x_i| = x^{+}_i + x^{-}_i$ s.t. $x^{+}_i , x^{-}_i \geq 0$.

However, if the problem is tweaked like this,

$min −2x_1 −x_2 + x_3 +|−13−12x_1 +5x_2 −7x_3|$

how can I reformulate this in a similar way with above?

Do I just need to introduce another variable $x_4$ and let $|x_4| = |-13-12x_1 + 5x_2 -7x_3|$? Then I guess the next step is $|x_4| = x^{+}_4 + x^{-}_4$. Then there might be a new constraint with $x_4^{+}, x_4^{-}$ but I am not sure.
I need your help!!!
Thanks a lot!
 A: You can add a constraint
$$x_4^+ - x_4^- = -13 - 12 x_1 + 5 x_2 - 7 x_3$$
($x_4^+, x_4^- \geq 0$)
and change objective to
$$\min \quad 2 x_1 - x_2 + x_3 + x_4^+ + x_4^-$$
A: We can think of an expression such as $|{−13−12x_1+5x_2−7x_3}|$ as
$$
   \max\{−13−12x_1+5x_2−7x_3, 13+12x_1-5x_2+7x_3\}.
$$
In general, we can write a linear program to minimize the maximum of two (or more) expressions. Say you have a program with objective function 
$$\text{minimize } \max\left\{\sum_{i=1}^n c_i x_i, \sum_{i=1}^n d_i x_i\right\}.$$ Then you can minimize a new variable $z$ subject to the two linear constraints $$z \ge \sum_{i=1}^n c_i x_i, \qquad z \ge \sum_{i=1}^n d_i x_i.$$
Since we are minimizing and want to satisfy both of these lower bounds, the best choice of $z$ will be to set it exactly equal to the larger of the two lower bounds.
In the example with absolute value, we can minimize $−2x_1−x_2+x_3+z$ subject to the constraints $$z \ge -13-12x_1+5x_2-7x_3$$ and $$z \ge 13 + 12x_1 - 5x_2 + 7x_3.$$
