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$ – Brian Borchers Apr 2 '20 at 2:25
  • $\begingroup$ Sure...I will try if I can convert my problem to integer variables. $\endgroup$ – Vinay Apr 2 '20 at 2:29
  • 1
    $\begingroup$ You can find helpful things in here: ibm.com/developerworks/community/forums/html/… $\endgroup$ – kur ag Apr 2 '20 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$ – LarrySnyder610 Apr 2 '20 at 20:42

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 '20 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 '20 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 '20 at 21:33

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.