2
$\begingroup$

I found a solution for just one term here

How can we formulate constraints of the form

$$ \sum_{i=1}^n |x_i -a_i| \ge K $$

in Mixed Integer Linear Programming ?

$\endgroup$
5
  • $\begingroup$ or.stackexchange.com/search?q=linearize+absolute+value+ $\endgroup$ Aug 18, 2022 at 11:05
  • $\begingroup$ None of those actually help, since the abs in those occurs in the objective which is minimized. Here one a needs a small epsilon approach to prevent one term from growing larger then abs and thereby fulfilling the inequality when it should no be fullfilled. $\endgroup$ Aug 18, 2022 at 11:47
  • 3
    $\begingroup$ Here is a very explicit reference. fico.com/fico-xpress-optimization/docs/latest/mipform/dhtml/… Then sum of the y's >= R $\endgroup$ Aug 18, 2022 at 12:42
  • 1
    $\begingroup$ That one works. Did big M over small epsilon. Neat. Do you wanna write up an answer post? $\endgroup$ Aug 18, 2022 at 13:32
  • $\begingroup$ Not really. That's why I wrote a comment. Have at it. Actually needs to be modified a bit to introduce a lower bound which might not be 0 as was assumed in the link. $\endgroup$ Aug 18, 2022 at 14:05

1 Answer 1

1
$\begingroup$

In CPLEX you can use the absolute value. For instance with the OPL API you can write

int n=5;
range r=1..n;

int K=10;

int a[i in r]=i;
dvar int x[r];

subject to
{
  sum (i in r) abs(x[i]-a[i])>=K;
}
$\endgroup$

Your Answer

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