0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ The first solution is not true. Pick $x=-2$, $x^+=2$ and $x^-=4$. Yet, we do not have that that $|x|=2\ne x^++x^-=6$. $\endgroup$
    – KBS
    Commented Mar 2, 2023 at 18:31
  • $\begingroup$ @KBS The trick is that the objective function will be minimized/maximized. If $x^+=2$ then $x^-=0$. $\endgroup$
    – callculus42
    Commented Mar 2, 2023 at 20:06
  • $\begingroup$ @callculus42 yeah but this is highly depending on context, which is quite missing here. $\endgroup$
    – KBS
    Commented Mar 2, 2023 at 20:39

1 Answer 1

Reset to default
0
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ It would be an integer linear programming if you use $z_1$ and $z_2$. So I think maximizing an absolute value can not be transformed to a linear programming. For the linear programming that minimizing an absolute value, my doubt is, the approach (B) seems easier than (A). If (A) and (B) is equivalent, why many textbook still use (A) instead of (B). $\endgroup$
    – zjdxsmjd
    Commented Mar 3, 2023 at 17:10

You must log in to answer this question.

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