linear-programmingmixed-integer-programminginteger-programming

How to write constraint with sum of absolutes in Integer Programming?

I found a solution for just one term here.

How can we formulate constraints of the form

|x1- a1| +|x2-a2| + .... + |xn - an| >= K

in Mixed Integer Linear Programming ?

Solution

  • Let's write this as:

     sum(i, |x[i]-a[i]|) >= K

    This is non-convex and needs special treatment. Sorry: this is not very simple.

    One way to model this is:

     x[i] - a[i] = zplus[i] - zmin[i]
 sum(i, zplus[i] + zmin[i]) >= K
 zplus[i] <= δ[i]*M[i]
 zmin[i] <= (1-δ[i])*M[i]
 zmin[i],zplus[i] >= 0
 δ[i] ∈ {0,1}

    Here M[i] are large enough constants. This needs some thought to find good values. Basically we want: M[i]=max(|x[i] - a[i]|).

    Alternative formulations are possible using indicator constraints and SOS1 variables. Some modeling tools and solvers have direct support for absolute values.