How to linearize difference of absolutes?

$$|a|\ge k|b|$$

where $a,b$ are variables and $k$ is a constant.

  • 1
    $\begingroup$ The feasible set isn’t convex so this can’t be done in linear programming. Do you want an answer involving integer variables? $\endgroup$ Apr 2, 2020 at 2:25
  • $\begingroup$ Sure...I will try if I can convert my problem to integer variables. $\endgroup$
    – Vinay
    Apr 2, 2020 at 2:29
  • 1
    $\begingroup$ You can find helpful things in here: ibm.com/developerworks/community/forums/html/… $\endgroup$
    – kur ag
    Apr 2, 2020 at 9:57
  • 1
    $\begingroup$ Please see the question and answer here: or.stackexchange.com/questions/3/…. If that doesn't answer your question sufficiently, then please revise your question to indicate what's still unanswered. $\endgroup$ Apr 2, 2020 at 20:42

1 Answer 1


Create some extra variables

$AB_1, AB_2, X_1, X_2, X_3, X_4$, and you have $a,b,k$

\begin{align}a &= X_1-X_2\\AB_1 &= X_1+X_2\\b &= X_3-X_4\\AB_2 &= X_3+X_4\\AB_1 &\geq k \cdot AB_2\end{align}

Also, you have to minimize variable $X_1, X_2, X_3, X_4$ and $X_1, X_2, X_3, X_4 \geq 0$

  • $\begingroup$ Is it possible to create constraints without objective function? I have another objective functions in my problem $\endgroup$
    – Vinay
    Apr 2, 2020 at 19:34
  • $\begingroup$ you can multiply it with an small value so that it doesn't have any impact on your objective function. Like this your current objective function + (x1+x2+x3+x4)*0.00000000001 some thing like this. You can also try it without adding objective function. $\endgroup$
    – ooo
    Apr 3, 2020 at 5:36
  • $\begingroup$ The small penalty approach is not entirely safe. If a solution with $|a|<k|b|$ produces a sizeable improvement in the objective function, the solver will "pad" $X_1$ and $X_2$ to make the solution look feasible and accept the small penalty. $\endgroup$
    – prubin
    Apr 3, 2020 at 21:33

Your Answer

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

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