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.tw...@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.tw...@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.barich...@univ-angers.fr>
> To: cschu...@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 <cschu...@kth.se>
>
>> Hi Vincent,
>>
>> Any idea?
>>
>> Cheers
>> Christian
>>
>> --
>> Christian Schulte, www.ict.kth.se/~cschulte/
>>
>> > -----Original Message-----
>> > From: bugs-boun...@gecode.org [mailto:bugs-boun...@gecode.org] On
>> > Behalf Of Gecode Bug Tracker
>> > Sent: Saturday, November 09, 2013 5:03 PM
>> > To: b...@gecode.org; joost.van.tw...@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.tw...@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
>> > b...@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@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
<<image/gif>>
<<image/gif>>
<<image/gif>>
<<image/gif>>
<<image/gif>>
<<image/gif>>
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
