Re: [Help-glpk] Absolute value constraint

[Dan Tulk]

Thank you all for your help. I wonder if it makes a difference when I explain 
the whole problem. I apologise for not doing so initially. What I'm *really* 
trying to solve is:

max f(x)

s.t.

f(x)/abs(g(x)) >= m

What is a good way to do this with a linear program?

Regards

Dan


----- Original Message ----
From: Michael Hennebry <address@hidden>
To: Andrew Makhorin <address@hidden>
Cc: Dan Tulk <address@hidden>; address@hidden
Sent: Tuesday, January 15, 2008 4:00:48 PM
Subject: Re: [Help-glpk] Absolute value constraint

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."


      
____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs