Consider the following (piecewise linear) minimization problem where $(x,y) \in \mathbb{R}^2$.
$$\begin{array}{ll} \text{minimize} & |x| + y\\ \text{subject to} & x + y = 2\\ & x \le 2\end{array}$$
Convert this into a linear program and solve it graphically.
My attempts (Updated)
Since $x,y$ are unconstrained
Let $x=x^++x^-,y=y^++y^-$
minimize $$z=x^++x^-+y^++y^-$$
subject to $$x^++x^-+y^++y^-=2$$ $$x^++x^-+s=2$$ $$x^+,x^-,y^+,y^-,s\ge0$$
That blue line is the objective function, and black region are union of all constraints
Now we take the intersection of all the constraints to get the region of feasible solution
Not hard to see, when $z=2$ the intersection of the objective function and that black line is all the optimal solution.
In another words, any convex combinations of $(0,2)$ and $(2,0)$ is a optimal solution.
See more detail about the definition of GLPP in this post.
What's the difference between GLPP and LPP
Is my answer correct$?$ And does LPP require all the constraints have same signs in $\{\ge,\le,=\}?$is it yet a form of LPP?
Is it ok to have unconstrained varibles in LPP $?$
Thanks for your help.
The only part of the original problem that violates linearity is the absolute value in the objective. Rewrite $x$ as $x^+ - x^-$ with $x^+ \ge 0$ and $x^- \ge 0$. Then replace $|x|$ with $x^+ + x^-$. Explicitly, the resulting LP is: \begin{align} &\text{minimize} & x^+ + x^- + y &\\ &\text{subject to} & x^+ - x^- + y &= 2\\ &&x^+ - x^- &\le 2 \\ &&x^+ \ge 0, x^- \ge 0, y \text{ free} \\ \end{align} If you want to solve it graphically, you can reduce to two variables by eliminating $y$, yielding: \begin{align} &\text{minimize} & 2x^- + 2 &\\ &\text{subject to} &x^+ - x^- &\le 2 \\ &&x^+ \ge 0, x^- \ge 0 \\ \end{align} In this form, it is clear that optimality requires $x^- = 0$, and the constraints then reduce to simple bounds $0 \le x^+ \le 2$. Any such $x^+$ is optimal, with $z=2$. You can then recover $(x,y)$ as $(x^+,2-x^+)$.