# Why is the following not a a linear programming problem?

$$\begin{array}{ll} \text{maximize} & 3x + 3y − 30\\ \text{subject to} & |x−2|−|y| \leq 5\end{array}$$

This is totally a LLP to me, just not in its standard form. I really don't know why it is not? What I am missing? Thanks!

• Notice that the constraint is not a linear function of your decision variables. – VHarisop Feb 2 '19 at 21:59
• @VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks? – Cathy Feb 2 '19 at 22:02
• Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$). – VHarisop Feb 2 '19 at 22:09
• @VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not? – Cathy Feb 2 '19 at 22:15
• I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not. – Micah Feb 3 '19 at 0:32

The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that $$S = \{(x,y)\in\Bbb{R}^2 \mid |x-2|-|y| \le 5\}$$ is not convex as $$(10,\pm3) \in S$$, but $$(10,0) \notin S$$.

This problem can be converted into an LPP by the usual trick in (2).

1. make the substitution $$u = x-2$$
2. split each decision variables into its positive and negative components.

\begin{alignat}{2} y^+ &:= \frac{|y|+y}{2} &\qquad y^- &:= \frac{|y|-y}{2} \\ u^+ &:= \frac{|u|+u}{2} & u^- &:= \frac{|u|-u}{2} \\ \therefore y &= y^+ - y^- & |y| &= y^+ + y^- \\ u &= u^+ - u^- & |u| &= u^+ + u^- \end{alignat} Then the objective function and the constraints become $$3u^+ - 3u^- + 3y^+ - 3y^- - 24$$ and $$\begin{cases} u^+ + u^- - y^+ - y^- &\le 5 \\ u^+, u^-, y^+, y^- &\ge 0 \\ u^+ u^- = y^+ y^- = 0 \end{cases}$$ respectively.

• your 'trick' is wrong (you can let $y^+ \to \infty$), you cannot convert it into an LPP without introducing binaries – LinAlg Feb 3 '19 at 1:24
• @LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189. – GNUSupporter 8964民主女神 地下教會 Feb 3 '19 at 9:36
• The original maximisation problem is unbounded (by fixing $x$ and letting $y \to +\infty$). Your suggestion ($y^+ \to +\infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something? – GNUSupporter 8964民主女神 地下教會 Feb 3 '19 at 9:46
• that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$). – LinAlg Feb 3 '19 at 13:30
• @LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$. – GNUSupporter 8964民主女神 地下教會 Feb 3 '19 at 15:24