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 <[EMAIL PROTECTED]> To: Andrew Makhorin <[EMAIL PROTECTED]> Cc: Dan Tulk <[EMAIL PROTECTED]>; [email protected] 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 [EMAIL PROTECTED] "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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
