Re: [Help-glpk] On strict inequalities conversion

[Paulo J. Matos]

On 06/02/06, Brady Hunsaker <address@hidden> wrote:
> 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.
>

I understand, as I've said later in the email I sent I do need strict
inequalities, and I'm not trying to maximixe or minimize. The issue is
that I'm trying to use GLPK to solve a non-optimization problem. I
just want to know about the feasibility of a set of constraints which
include strict inequalities. It's just to compare GLPK performance
with other specific algorithms like FourierMotzkin elimination,
OmegaTest, etc. This is why I'm forcing the use of GLPK and strict
inequalities in a non-optimization problem.

Thanks for your explanation. I'll proceed with this to solve Linear
Real Arithmetic then, i.e., non-optimization problems involving weak
and strict inequalities with real variables.

Cheers,

Paulo Matos

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

Yes, thanks, that's done! :)

> 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/
>


--
Paulo Jorge Matos - pocm at sat inesc-id pt
Web: http://sat.inesc-id.pt/~pocm
Computer and Software Engineering
INESC-ID - SAT Group