# Linear programming with absolute values

I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ?

Example of use of absolute values:

Minimize |a+b+c| + |a-c| s.t.
|a| + b > 3
| |a| - |b| | <= 5
| |b| - 3 | = 0


All constraints in a linear program are convex (if $x,y$ satisfy the constraints, then $tx+(1-t)y$ also does for all $0 \leq t \leq 1$). The constraint $|a|+b > 3$ is not convex, since $(4,0)$ and $(-4,0)$ are both solutions while $(0,0)$ is not. It is also not closed, which is another reason why you cannot use it in a linear program (change $>$ to $\geq$). The constrict $|a|+b \leq 3$, however, can be used, since it is equivalent to the pair of constraints $a+b \leq 3$ and $(-a)+b \leq 3$.

So absolute values can sometimes be expressed in the language of linear programming, but not always.

• ok, i'm more interested in relaxation of integer programs so i could replace $|a|+b<3$ by $|a|+b≤2$ i guess. Moreover, i could also use this kind of tricks to handle the case of $|a|$ : stackoverflow.com/a/28933583/3476917. So my question is probably a bit different: is it always possible to use absolute values with the simplex algorithm ? I think that we can repeat the same trick to remove all absolute values. – permanganate Jul 24 '15 at 14:40
• No, probably not. The trick only works when the absolute values appear with positive coefficients on the left-hand side of an at-most inequality. It won't work the other way around. Note also that if you're doing integer programming then you aren't really using the simplex algorithm (though I'm not sure it matters). – Yuval Filmus Jul 24 '15 at 14:44

I've found out a very interesting document that answers my question: http://lpsolve.sourceforge.net/5.5/absolute.htm It's about integer programming and it covers all possible cases I think. See section >= minimum to handle abs(X) >= minimum. Here is another one with more tricks: http://orinanobworld.blogspot.de/2012/07/modeling-absolute-values.html

There are several methods described in the links above. The "Binary method" is exactly what I wanted: let's assume you want to remove $$|x|$$ ($$x$$ is a variable) wherever it appears in your program, and you know that $$|x|$$ cannot be greater than a constant $$m$$. Then, perform the following:

• add new variables $$x^+$$, $$x^-$$ and $$b$$
• add constraint $$x = x^+ - x^-$$
• add constraints $$b \in \left\{0,1\right\}$$, $$0 \leq x^+ \leq b \cdot m$$ and $$0 \leq x^- \leq (1-b) \cdot m$$
• replace $$|x|$$ by $$x^+ + x^-$$ wherever it appears
• Integer programming is another kettle of fish entirely. Your auxiliary variable $b$ essentially splits the problem into two separate linear programming problems, of which you select the best optimum. Each such variable doubles the number of problems to solve... – vonbrand Jul 25 '15 at 0:59
I think you can just get rid of |x| if you slightly modify the simplex algorithm. Only variables that are in the basis set can ever be > 0. So you let $$x = x^+ - x^-$$ with the additional condition that $$x^+$$, $$x^-$$ are not non-zero at the same time, and replace $$|x| = x^+ + x^-$$. You enforce the condition by not allowing $$x^+$$ and $$x^-$$ into the basis set at the same time.