1
$\begingroup$

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!

$\endgroup$

2 Answers 2

5
$\begingroup$

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^-$$

$\endgroup$
1
  • $\begingroup$ Thanks, I think I got some clues! $\endgroup$ Commented May 1, 2019 at 12:28
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Actually I wanted to utilize add two variables (x+, x-) but still I think your answer is a general way of solving the LP problem with absolute values. Thank you! $\endgroup$ Commented May 1, 2019 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .