Re: [Help-glpk] On strict inequalities conversion

[Brady Hunsaker]

Paulo J. Matos wrote:
> On a reply by Andrew Makhorin dated Fri, 9 Aug 2002 20:10:32 +040:
> http://lists.gnu.org/archive/html/help-glpk/2002-08/msg00004.html
> 
> Andrew says the one can transform a lower strict bound to a lower weak bound 
> as:
> eps = 10.0 * lpx_get_real_parm(lp, LPX_K_TOLBND);
> new_lb = old_lb + eps * (1.0 + fabs(old_lb));
> 
> Why not ?
> new_lb = old_lb + lpx_get_real_parm(lp, LPX_K_TOLBND);
> ?
> 

The reason this may not work is that GLPK's tolerance is not absolute;
it is a percentage of the actual value.  That's why he recommends
multiplying by fabs(old_lb).  The "1.0 +" is just there in case old_lb
is zero.

More generally, I would say that I recommend against this approach
unless you know why you need the strict inequality.  It generally
doesn't make sense to have a strict inequality in an optimization
problem.  Say your bound is 2.0.  Are you willing to accept 1.99?  How
about 1.99999999?  If you'll accept the latter, then you might as well
accept 2.0; computer arithmetic isn't good enough to differentiate the
two anyway (after a long series of rounding errors).  If you're not
willing to accept 1.9999999, then just figure out where you draw the
line and make a weak inequality at that point.

If you're working with integers, on the other hand, then strict
inequalities can be converted into weak inequalities easily.

Brady

> Still, if I have an upper bound not in a variable but a constraint upper 
> bound:
> maximize 0: (which means I don't need to maximize, I need _any_ solution)
> sum a_i x_i < b
> 
> can I do:
> eps = 10.0 * lpx_get_real_parm(lp, LPX_K_TOLBND);
> newb = b - eps*(1.0 + fabs(b));
> 
> and solve
> sum a_i x_i <= newb?
> 
> Is this the correct way (best way) to work around this issue?
> 
> Cheers,
> --
> Paulo Jorge Matos - pocm at sat inesc-id pt
> Web: http://sat.inesc-id.pt/~pocm
> Computer and Software Engineering
> INESC-ID - SAT Group
> 

-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/