[gecode-users] Rounding behavior of relational constraints
Vincent Barichard
Vincent.Barichard at univ-angers.fr
Wed Nov 13 09:46:12 CET 2013
Dear all,
Indeed, in propagators, for example the "Linear" propagator internal
calculations are done to update bounds of variables. If the maximum float
value is involved in these calculation it may leads to rounding result
behaviors defined in the IEEE floating rules. There is no way to avoid it
but the computes remain correct. Even if the bounds are not as tight as
expected after a call to "propagate", no solution is lost. After a
branching, the interval will be cut and most of the time the bounds
propagate as expected.
To illustrate these floating rounding behaviors, please consider the
following C++ code :
#include <iostream>
#include <limits>
using namespace std;
int main() {
float mx = std::numeric_limits<float>::max();
cout << "Max float value mx=" << mx << endl;
cout << "Addition with a small constant: mx+2=" << mx + 2 << endl;
cout << "Equality test with addition with a small constant: mx+2==mx ? =
" << (((mx + 2)==mx)?"TRUE":"FALSE") << endl;
cout << "Addition with a bigger constant: mx+mx/2=" << mx + mx/2 << endl;
cout << "Equality test with addition with a bigger constant: mx+mx/2==mx
? = " << (((mx + mx/2)==mx)?"TRUE":"FALSE") << endl;
cout << "Order of computes 1 : mx+2-mx= " << mx+2-mx << std::endl;
cout << "Order of computes 2 : mx-mx+2= " << mx-mx+2 << std::endl;
return 0;
}
gives :
Max float value mx=3.40282e+38
Addition with a small constant: mx+2=3.40282e+38
Equality test with addition with a small constant: mx+2==mx ? = TRUE
Addition with a bigger constant: mx+mx/2=inf
Equality test with addition with a bigger constant: mx+mx/2==mx ? =
FALSE
Order of computes 1 : mx+2-mx= 0
Order of computes 2 : mx-mx+2= 2
As you see, different results are computed depending of the value of the
constants and even of the order of the computes. Keep in mind that no
solution will be lost. The best advice I can give is to set initial bounds
of variables as tight as possible to make propagation as efficient as it
can be.
Regards,
Vincent Barichard
2013/11/12 Joost van Twist <joost.van.twist at quintiq.com>
> Dear all,
>
> When using a relational constraint between two or more floating variables
> the bounds might not be always updated as you would expect during
> propagation. This happens only when being close to the maximum limits of
> floats. Why does this happen?
>
> I have attached an example program. It has two variables and adds a
> constraint stating that the second variable should be bigger than the first
> plus some small constant. The lower bound of the second variable remains
> zero however under some conditions.
>
> First I thought is was some kind of bug, but after posting a report, it
> appeared to be because of some rounding side effects and it is not an issue
> when the bounds shrink. Christian suggested to repost it as question. I
> have also attached the initial answer Vincent gave who worked on the
> floating module.
>
> Kind regards,
>
>
>
>
>
>
>
>
>
>
>
> [image: Quintiq logo] <http://www.quintiq.com/> Joost van Twist Software
> Engineer R&D Optimization Team *Quintiq* T +31 73 691 0739 M +31 63 179
> 1690 E joost.van.twist at quintiq.com www.quintiq.com [image: Twitter]<http://twitter.com/quintiq> [image:
> Facebook] <http://www.facebook.com/Quintiq> [image: LinkedIn]<http://www.linkedin.com/company/quintiq> [image:
> YouTube] <http://www.youtube.com/channelquintiq> Please consider the
> environment before printing this email.
>
>
> ---------- Message transféré ----------
> From: "Vincent Barichard" <Vincent.Barichard at univ-angers.fr>
> To: cschulte at kth.se
> Cc:
> Date: 10 Nov 2013 22:17:11 +0100
> Subject: Re: FW: [Gecode-bugs] New bug: Relational constraint gives
> inconsistent lowerbound for floating variables
> Hi Christian,
>
> I looked quickly (I'm not at home for now) and I think that the bug is in
> the compute
> of the sl and sly variables (see propagate of Lq<P,N> of linear/nary.hpp).
> Indeed, the upper bound is set to FLOAT_MAX, and as a consequence some
> compute failed.
> When sl is computed (lines 353 and 356) we get : FLOAT_MAX + -2 =
> FLOAT_MAX,
> When sly is computed (line 374) we get : FLOAT_MAX - sl =
> 6.9533558075717661e-310 (almost 0)
>
> The order of the computes has an effect on the result. I put here after an
> example
> taken from gdb :
> (gdb) p y[i].max() + 2 - y[i].max()
> $30 = 0
> (gdb) p y[i].max() - y[i].max() + 2
> $31 = 2
>
> In an ideal world we would get sly = FLOAT_MAX - FLOAT_MAX + 2 = 2
> It will work after a cut (during search) but a call to status() is not
> enough to get
> some reductions.
>
> I don't know an easy fix. The only way I see is to identify the FLOAT_MAX
> cases each time it is encountered and to make some special cases. You may
> have another idea ?
>
> Just a thought. I ever encountered these cases in the past, calculations
> are not wrong, and most of the time, tighter bounds of the variables when
> modeling solves the problem. It may occur in many propagators each time a
> compute involves FLOAT_MAX.
>
> Cheers,
> Vincent
>
>
> 2013/11/10 Christian Schulte <cschulte at kth.se>
>
>> Hi Vincent,
>>
>> Any idea?
>>
>> Cheers
>> Christian
>>
>> --
>> Christian Schulte, www.ict.kth.se/~cschulte/
>>
>> > -----Original Message-----
>> > From: bugs-bounces at gecode.org [mailto:bugs-bounces at gecode.org] On
>> > Behalf Of Gecode Bug Tracker
>> > Sent: Saturday, November 09, 2013 5:03 PM
>> > To: bugs at gecode.org; joost.van.twist at quintiq.com
>> > Subject: [Gecode-bugs] New bug: Relational constraint gives inconsistent
>> > lowerbound for floating variables
>> >
>> > New bug report for Gecode from Joost van Twist
>> (joost.van.twist at quintiq.com).
>> >
>> > Summary: Relational constraint gives inconsistent lowerbound for
>> floating
>> > variables
>> >
>> > Gecode version: 4.2.0
>> > Platform: Windows
>> >
>> > Details:
>> > /*
>> > The following program posts a simple relation between two float
>> variables.
>> The
>> > lowerbound of variable b remains zero while it should become 2. It does
>> become
>> > 2 when changing the upperbound of b to a smaller value (1000 for
>> example).
>> > Also when using the \">\" operator the lowerbound of b will be 2 as
>> well.
>> > */
>> >
>> > #include \"gecode/float.hh\"
>> > #include \"gecode/minimodel.hh\"
>> >
>> > using namespace Gecode;
>> >
>> > class TestModel : public Gecode::Space
>> > {
>> > public:
>> > FloatVar a;
>> > FloatVar b;
>> >
>> > TestModel()
>> > : a(*this,0, 0),
>> > b(*this,0, Gecode::Float::Limits::max) //using an upper bound
>> significantly
>> > smaller is also a workaround
>> > {
>> > rel(*this, b >= a + 2.0); //lower bound of b will stay 0, when
>> changing to \">\"
>> > works fine
>> > //rel(*this, b == 0); //will still make the space correctly
>> infeasible
>> > }
>> >
>> > TestModel(bool share, TestModel& testmodel)
>> > : Space(share, testmodel)
>> > {
>> > a.update(*this, share, testmodel.a);
>> > b.update(*this, share, testmodel.b);
>> > }
>> >
>> > virtual Gecode::Space* copy(bool share)
>> > {
>> > return new TestModel(share, *this);
>> > }
>> >
>> > virtual void print(std::ostream& os) const
>> > {
>> > os << \"a: \" << a << \" b: \" << b << std::endl;
>> > }
>> > };
>> >
>> >
>> > int main(int argc, char* argv[])
>> > {
>> > TestModel model;
>> >
>> > if ( model.status() == SS_FAILED )
>> > {
>> > std::cout << \"infeasible\" << std::endl;
>> > } else
>> > {
>> > std::cout << \"feasible\" << std::endl;
>> > }
>> >
>> > model.print(std::cout);
>> >
>> > return 0;
>> > }
>> >
>> > _______________________________________________
>> > bugs mailing list
>> > bugs at gecode.org
>> > http://www.gecode.org/cgi-bin/mailman/listinfo/bugs
>>
>>
>
>
> --
> Vincent Barichard Université d'Angers (LERIA)
> Tel: 02 41 73 52 06 Département Informatique
> Fax: 02 41 73 50 73 H203
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
--
Vincent Barichard Université d'Angers (LERIA)
Tel: 02 41 73 52 06 Département Informatique
Fax: 02 41 73 50 73 H203
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 285 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0006.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 233 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0007.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 2801 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0008.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 255 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0009.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 692 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0010.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 396 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20131113/51e61d4a/attachment-0011.gif>
More information about the users
mailing list