Convert the non linear problem into standard minimization linear programming form

Question

I have to convert the non linear problem into standard minimization linear programming form

Minimize: $|x|+|y|+|v|$

Subject to: $$x+y\le1$$ $$2x+v=3$$

I dont have any idea how can I do it...I would appreciate any help.

score 4 · Accepted Answer · answered Nov 18 '14 at 18:02

4

Hint: Write $x$ as $$x=x^+-x^-$$ with $x^+, x^-\ge 0$. Now $$|x|=x^++x^-$$ Similarly for $y,v$.

answered Nov 18 '14 at 18:02

Jimmy R.

Can you check my answer..what if x+ and x- are both positive? – luka5z Nov 19 '14 at 10:29
1

Yes, I think it is a correct answer, sorry I did not see it earlier +1. Say $x^+=5$ and $x^-=3$ is a solution, then $x^+=2$, $x^-=0$ is a solution and a better one (with respect to your objective function), so do not worry if they are both positive. – Jimmy R. Nov 19 '14 at 10:34

score 3 · Answer 2 · answered Nov 19 '14 at 12:17

3

A simpler way:

$min \quad t_x+t_y+t_z$

$ s.t. $

$ x+y\leq 1$

$ 2x + z =3 $

$ t_i \geq i \quad i\in\{x,y,z\} $

$ t_i \geq -i \quad i\in\{x,y,z\} $

That should work.

answered Nov 19 '14 at 12:17

AndreaCassioli

can you explain more? – luka5z Nov 19 '14 at 17:59
1

Since you are minimizing, at the optimum $t_i=i$ if $i\geq 0$ or $t_i=-i$ if $i\leq 0$. Thus $t_i=|i|$. – AndreaCassioli Nov 20 '14 at 16:18

score 1 · Answer 3 · answered Nov 18 '14 at 18:10

1

Minimize $x^{+}+x^{-}+y^{+}+y^{-}+v^{+}+v^{-}$

Subject to

$$x^{+}-x^{-}+y^{+}-y^{-}+s=1$$ $$2x^{+}-2x^{-}+v^{+}-v^{-}=3$$ $$x^{+}, x^{-}, y^{+}, y^{-}, v^{+}, v^{-}, s \ge 0$$

Is a correct answer?

answered Nov 18 '14 at 18:10

luka5z

3 Answers3