Two approaches to change the absolute value in Linear Programming

119 Views Asked by At

Usually a MP with absolute value $|x|$ can be linearlize by using the transformation of $$|x|=x^++x^- \ \ and \ \ x=x^+-x^-. (A)$$ But I find someone also use $$y\geq x \ \ and \ \ y\geq -x. (B)$$ to replace $|x|$ by $y$.

Is the approach (B) equivalent to, or more powerful than (A)?

(A) can only be used, as I think, when the objective is $\min c|x|$ with $c>0$. When $c<0$, or the absolute value appears in the constraints, generally it is not work.

In which situation (B) can be used? More broader than that of (A), or more narrower?

If the objective is $\max c|x|$ with $c>0$, can we use $$y\leq x \ \ and \ \ y\leq -x. (C)$$ to replace $|x|$ by $y$?

Why (B) (or (C)) can not be used when the absolute value appears in the constraints?

1

There are 1 best solutions below

1
On

Logically if you are dealing with min $\vert x \vert$ as objective, it implies you need a variable that will be $\gt 0$. so one way is (B). However if objective is max $ \vert x \vert$, then your variable $(-)x \le y $ will be unbounded and if by $y \le -x$ it wont represent the absolute value. So one way is
$ y \le x + Mz_1$
$ y \le -x +Mz_2$
$ z_1+z_2 =1 $
$ 0 \le y$