Reformulate the following optimization problem as a linear program.

$$\begin{array}{ll} \text{minimize} & 2 x_1 + 3 |x_2-10|\\ \text{subject to} & |x_1+2|+|x_2|\leq 5\end{array}$$

First, I tried the following. If $y=x_1+2=y^+-y^-$, then $|x_1+2|=y^++y^-$, where $y^+, y^-\geq 0$. Now, if $z=x_2-10=z^+-z^-$, then $|x_2-10|=z^++z^-$, $z^+, z^- \geq 0$.

But the problem appear when I try to express $|x_2|$ in terms of $z^+, z^-$, because I get an inequality of $|x_2|$ and not an equality, i.e, $|x_2|=|z^+-z^-+10|\leq |z^+-z^-|+10= z^++z^-+10$.

Could you give me a suggestion?


Just do the same trick a third time:

If $w = x_2 = w^+ - w^-$ then $|x_2| = w^+ + w^-$, $w^+, w^- \ge 0$. Or even simpler just use $x_2 = x_2^+ - x_2^-$, then $|x_2| = x_2^+ + x_2^-$, $x_2^+, x_2^- \ge 0$.

In other words, each absolute value term gets its own decomposition into positive and negative parts, even if some of the absolute value terms share a decision variable.

  • $\begingroup$ I did that, but appear a decision variable in the constraint that isn't relationed with the function to minimize, doesn't matter? $\endgroup$ – SSG19 May 27 '19 at 2:00
  • $\begingroup$ It's common to have decision variables in constraints that don't appear directly in the objective function. The key is that those variables are connected (via constraints) to other variables, and those variables are in the constraints. $\endgroup$ – LarrySnyder610 May 27 '19 at 2:05

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.