5
$\begingroup$

How to linearize difference of absolutes?

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

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

$\endgroup$
4
  • 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 '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
2
$\begingroup$

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$

$\endgroup$
3
  • $\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.