[gecode-users] Rounding behavior of relational constraints

[Joost van Twist]

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,












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 
    
Please consider the environment before printing this email.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20131112/f5e5e02c/attachment-0001.html>
-------------- 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/20131112/f5e5e02c/attachment-0006.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/20131112/f5e5e02c/attachment-0007.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/20131112/f5e5e02c/attachment-0008.gif>
-------------- 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/20131112/f5e5e02c/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/20131112/f5e5e02c/attachment-0010.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/20131112/f5e5e02c/attachment-0011.gif>
-------------- next part --------------
An embedded message was scrubbed...
From: "Vincent Barichard" <Vincent.Barichard at univ-angers.fr>
Subject: Re: FW: [Gecode-bugs] New bug: Relational constraint gives	 inconsistent lowerbound for floating variables
Date: 10 Nov 2013 22:17:11 +0100
Size: 14147
URL: <http://www.gecode.org/pipermail/users/attachments/20131112/f5e5e02c/attachment-0001.mht>
-------------- next part --------------
#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;
}