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!
Best Answer
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^-$$