9
$\begingroup$

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
Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – permanganate
    Jul 24, 2015 at 14:40
  • 1
    $\begingroup$ 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). $\endgroup$
    – Yuval Filmus
    Jul 24, 2015 at 14:44
8
$\begingroup$

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
Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you summarize the main idea in your answer? We frown on link-only answers, where all the content is found on the other page: we don't want to be just a link farm; and also if the link rots or stops working, then the answer becomes worthless. I think this would indeed be valuable to have here, but please summarize the main idea in your own words in your answer. Thank you! $\endgroup$
    – D.W. ♦
    Jul 24, 2015 at 17:01
  • $\begingroup$ I've added some details about the Binary method (the 2 links provide more methods but this one is enough to solve my problem) $\endgroup$
    – permanganate
    Jul 24, 2015 at 17:32
  • $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Jul 24, 2015 at 17:45
  • $\begingroup$ 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... $\endgroup$
    – vonbrand
    Jul 25, 2015 at 0:59
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.