How to linearize difference of absolutes?

Question

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

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

The feasible set isn’t convex so this can’t be done in linear programming. Do you want an answer involving integer variables? — Brian Borchers, Apr 02 '20 at 02:25
Sure...I will try if I can convert my problem to integer variables. — Vinay, Apr 02 '20 at 02:29
You can find helpful things in here: https://www.ibm.com/developerworks/community/forums/html/topic?id=7518cd88-d670-460f-8f9a-aafffe8fc9a1 — kur ag, Apr 02 '20 at 09:57
Please see the question and answer here: https://or.stackexchange.com/questions/3/working-with-absolute-values-in-constraint-in-a-lp-or-milp. If that doesn't answer your question sufficiently, then please revise your question to indicate what's still unanswered. — LarrySnyder610, Apr 02 '20 at 20:42

score 2 · Answer 1 · edited Apr 02 '20 at 15:03

2

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$

edited Apr 02 '20 at 15:03

answered Apr 02 '20 at 14:31

ooo

Is it possible to create constraints without objective function? I have another objective functions in my problem – Vinay Apr 02 '20 at 19:34
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. – ooo Apr 03 '20 at 05:36
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. – prubin Apr 03 '20 at 21:33

1 Answers1