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. Commented Jul 24, 2015 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). Commented Jul 24, 2015 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
– D.W.
Commented Jul 24, 2015 at 17:01
• I've added some details about the Binary method (the 2 links provide more methods but this one is enough to solve my problem) Commented Jul 24, 2015 at 17:32
• Perfect, thank you! P.S. On this site we try to avoid "stuff. edit: more stuff"; instead, edit the answer to read coherently in its entirety and be what it should have been from the start, as we want to build an archive of high-quality questions and answers that will be useful to others in the future. I've edited your answer for you but wanted to mention this for your consideration for the future. Thanks for the helpful answer!
– D.W.
Commented Jul 24, 2015 at 17:45
• 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... Commented Jul 25, 2015 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.

I've not tried this actually :-( But a variation where I didn't want a variable to be restricted to positive values (just x ≤ 3 instead of 0 ≤ x ≤ 3) worked very well this way.