0
$\begingroup$

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

enter image description here

Now we take the intersection of all the constraints to get the region of feasible solution

enter image description here

Not hard to see, when $z=2$ the intersection of the objective function and that black line is all the optimal solution.

enter image description here

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $?$ $\endgroup$ – Manx Oct 5 '19 at 20:34
  • $\begingroup$ Is it ok to have unconstrained varibles in LPP $?$ $\endgroup$ – Manx Oct 5 '19 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Rob Pratt Oct 5 '19 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.