Re: [Help-glpk] Absolute value constraint

[Michael Hennebry]

On Tue, 15 Jan 2008, Andrew Makhorin wrote:

> > Hi, is it possible to express 'abs(f(x)) >= m' as a linear constraint?
>
> Yes, using a mip approach.

That requires a nonlinear constraint,
but since it can't be done with only linear constraints,
I'll forgive you.

> There are two alternatives:
>
>    f(x) >= 0 that gives f(x) >= m
>
>    f(x) <  0 that gives -f(x) >= m or, eqiuvalently, f(x) <= -m.
>
> Let z be a binary variable such that:
>
>    z = 1 means m <= f(x) <= +M
>
>    z = 0 means -M <= f(x) <= -m
>
> where M is a "big" constant. Then the constraint can be formulated
> as follows:

Big-M is usually a bad idea.
Big-M's come in two sizes: too small to be
correct and too big for computational accuracy.

Doing it right requires bounds on f.
Suppose we have L and U such that L<=-m, m<=U, and L<=f(x)<=U .

z=1 implies  U>=f(x)>=m
z=0 implies -m>=f(x)>=L
     z*(U+m)-m>=f(x)>=L+z*(m-L)

> m * z - M * (1 - z) <= f(x) <= M * z - m * (1 - z)
>
> (under assumption that f(x) is a linear function of variables).

-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."