How to linearize difference of absolutes?
$$|a|\ge k|b|$$
where $a,b$ are variables and $k$ is a constant.
$\begingroup$
$\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$– Brian BorchersApr 2, 2020 at 2:25
-
$\begingroup$ Sure...I will try if I can convert my problem to integer variables. $\endgroup$– VinayApr 2, 2020 at 2:29
-
1$\begingroup$ You can find helpful things in here: ibm.com/developerworks/community/forums/html/… $\endgroup$– kur agApr 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$– LarrySnyder610Apr 2, 2020 at 20:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$– VinayApr 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.00000000001some thing like this. You can also try it without adding objective function. $\endgroup$– oooApr 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