3
$\begingroup$

$$\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!

$\endgroup$
  • $\begingroup$ Notice that the constraint is not a linear function of your decision variables. $\endgroup$ – VHarisop Feb 2 at 21:59
  • $\begingroup$ @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? $\endgroup$ – Cathy Feb 2 at 22:02
  • $\begingroup$ 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$). $\endgroup$ – VHarisop Feb 2 at 22:09
  • $\begingroup$ @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? $\endgroup$ – Cathy Feb 2 at 22:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Micah Feb 3 at 0:32
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ your 'trick' is wrong (you can let $y^+ \to \infty$), you cannot convert it into an LPP without introducing binaries $\endgroup$ – LinAlg Feb 3 at 1:24
  • $\begingroup$ @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. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 3 at 9:36
  • $\begingroup$ 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? $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 3 at 9:46
  • $\begingroup$ 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$). $\endgroup$ – LinAlg Feb 3 at 13:30
  • $\begingroup$ @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$. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 3 at 15:24

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.