1
$\begingroup$

I'm attempting to reformulate a linear program into standard form. Part of this problem requires me to eliminate absolute values from all of my variables. Specifically, I have the problem: \begin{align*} &\min_{x\in \mathbb{R}^2} 2x_1 + 3|x_2-10|\\ &\text{Subject to } |x_1+2| + |x_2| \le 5 \end{align*} I have determined the following:

Let $$x_2^+:=\max\{x_2-10,0\}$$

and

$$x_2^-:=\max\{-x_2+10,0\}$$

Then $$|x_2-10| = x_2^++x_2^- \text{ and } x_2-10 = x_2^+-x_2^-$$ Here, we note that $x_2^+, x_2^- \ge 0$.

What I need is some way to express $|x_2|$ in terms of $x_2^+$ and $x_2^-$ that doesn't use absolute value bars.

I've tried several things on this front, but I keep getting stuck. Do I need to introduce more variables to make this work? Any hints or insight would be greatly appreciated.

Note: I don't actually need to know the solution to this linear program.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The abolute value is a simple and useful concept. If you don't want to use it, you may find an alternative form which also works. However I expect that things only become more complicated. My advise is not to spend time and effort on this aspect of your program. $\endgroup$ – M. Wind Oct 28 '18 at 5:23
  • $\begingroup$ @M.Wind I agree that doing this for every question is overkill- But it's important for the OP to understand that linear programs with absolute values are still standard linear programs, and that the absolute values do not invalidate the linearity. $\endgroup$ – DreamConspiracy Oct 28 '18 at 6:38
  • $\begingroup$ |x| = $\sqrt {x^2}$ $\endgroup$ – William Elliot Oct 28 '18 at 8:45
  • $\begingroup$ @WilliamElliot while that is an interesting approach, I should have clarified that I need the problem to remain a linear program, so all of the constraints should remain linear too. $\endgroup$ – BSplitter Oct 28 '18 at 16:35
  • $\begingroup$ @BSplitter indeed you need to introduce more variables, one set per absolute value $\endgroup$ – LinAlg Oct 28 '18 at 19:41
0
$\begingroup$

The first step is usually to introduce new variables, but with inequalities: \begin{align*} &\text{minimize} &&2x_1 + 3t_1\\ &\text{Subject to } &&t_2 + t_3 \le 5,\\ &&&|x_2-10|\le t_1,\\ &&&|x_1+2|\le t_2,\\ &&&|x_2|\le t_3. \end{align*} Note that the solution is the same (obviously an upper bound plus equalities are included).

The second step is to observe that e.g. $$ |x_2-10|\le t_1\iff -t_1\le x_2-10\le t_1 $$ etc, that is each absolute value inequality can be replaced by two linear ones.

The price to pay: increased dimension.

The gain (?): linear programming software.

|cite|improve this answer
$\endgroup$

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.