|
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,
|
--- Begin Message ---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
Header
Description: Binary data
--- End Message ---
#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;
}_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
