# Minimization problem with absolute value in objective function

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.

## 1 Answer

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^+)$$.

• 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$$ Like this $?$ – Manx Oct 5 '19 at 20:34
• Is it ok to have unconstrained varibles in LPP $?$ – Manx Oct 5 '19 at 20:35
• Yes, free variables are fine, but you should have $x^+ - x^-$ instead of $x^+ + x^-$ in the constraints. Also, there is no reason to introduce $y^+$, $y^-$, or $s$. See my updated answer. – Rob Pratt Oct 5 '19 at 21:55