[gecode-users] Critical bug.

[Guido Tack]

Hi.

> The problem is in ViewValBranching:
>
> 1.- The status method calculate the "start" variable.
>
> 2.- The description method create the branch description, with the
> position and value of the variable to make the branch. _The position
> is absolute_.
>
> 3.- The commit, impose the branch description, since the position is
> absolute, _position is position minus offset_ , but the offset depends
> of the start variable, but status method in the recomputation phase is
> not called, so the start variable is  zero. This produces that the
> offset is distinct between the original node and the recompute one,

This is exactly what is supposed to happen!
The ViewValBranching contains the absolute position in the original array.
The offset determines how many variables have been eliminated from the
array. It does _not_ depend on the start variable, but on how many times
x.drop_fst(start) was called. If never, then offset=0. If fewer times than
when the branching was created, offset will be smaller than it was during
creation.

So the invariant is that the description contains the absolute index, and
that offset determines how many variables have been removed from the
beginning of the array. That should be enough to redo the decisions
precisely.

> I think that the error is critical, because produce that the
> recomputation fix other variables, and we lost sector of the search
> space.

That is really a little bizarre, because we have checked the search space
for all our problems, and all the time recomputation works just fine. If
you're still convinced that this is a bug, please convince us ;-) It would
be great if you could send us a small example that behaves strange when
doing recomputation.

Cheers,
   Guido

-- 
Guido Tack
http://www.ps.uni-sb.de/~tack