search

miguelkachondo / or-tools

Automatically exported from code.google.com/p/or-tools
0 stars 0 forks source link

Bug in PositiveTableConstraint::InitialPropagate #6

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
On some instances, there is an assertion failure when 
PositiveTableConstraint::InitialPropagate calls IntervalUp64.

You pass position+1 as argument, but position can have any value between 0 and 
63. If it is 63, then you call IntervalUp64(64) which leads to the assertion 
failure.

If you run the program with NDEBUG, this leads to an infinite loop.

The trivial solution would be to add a check, but maybe there's something 
smarter that can be done.

Original issue reported on code.google.com by phil.v...@gmail.com on 16 Sep 2011 at 5:55

GoogleCodeExporter commented 9 years ago 
From what I understand from the code you could write it like this, solving the 
problem and making it faster :

virtual void InitialPropagate() {
  // Build active_ structure.
  for (int var_index = 0; var_index < arity_; ++var_index) {
    for (ConstIter<hash_map<int64, uint64*> > it(masks_[var_index]); !it.at_end(); ++it) {
      if (!vars_[var_index]->Contains(it->first)) {
        for (int i = 0; i < length_; ++i) {
          active_tuples_[i] &= ~(active_tuples_[i] & it->second[i]);
        }
      }
    }
  }
  (...)
}

Original comment by phil.v...@gmail.com on 16 Sep 2011 at 6:17

GoogleCodeExporter commented 9 years ago 
I will have a look right away.
Thanks for the bug report.

Original comment by laurent....@gmail.com on 17 Sep 2011 at 8:26

GoogleCodeExporter commented 9 years ago 
I have added you suggestion and cleaned up the code around.
Thanks!

Original comment by laurent....@gmail.com on 17 Sep 2011 at 8:49