[gecode-users] commit on already-assigned variable

[kellen at cretin.net]

Hej!

I'm working on implementing bit-vector variables in gecode, following the
example given in MPG.

A part of this is providing relevant View selection for the brancher. I have
done so with a NONE implementation which also follows the model given in MPG,
which returns parameterized a ViewSelNone:

    return new (home) ViewSelNone<BitView>(home, bvb);

Where BitView is the type of views on the variable implementations (typedef'd
as unsigned int), and bvb is a "BitVarBranch". So far, so good.

Later, I have defined a ValCommit class, including a commit function:

    ModEvent commit(Space& home, unsigned int a, BitView x, int i, BitType n);

Since I am branching based on the values of certain bits of the BitView x,
there are only two alternatives (a == 0, a != 0). The parameter n provides a
mask with only a single set bit which determines the bit on which branching
occurs. 

My issues is that the search engine appears to be calling commit() on
already-assigned variables which violates a check I have implemented there to
validate the input as well as violates my expectation of how the engine should
function with a NONE-typed variable/view selection.

Specifically, I have an array of 64 4-bit bitvector variables and at some
point during search, commit() is called on variable 56, which is already
assigned. I have verified in GDB that the variable is, in fact, assigned. I
can see in GDB that this variable is branched on a number of times before
failure. The relevant backtrace when failure occurs:

#0  BV::Bit::ValCommitBitSplit::commit (this=0x9972500, home=..., a=0, x=..., i=56, n=1) at src/bitvec/branch.cpp:144
#1  0x08068331 in Gecode::ValSelCommit<BV::Bit::ValSelRndBit, BV::Bit::ValCommitBitSplit>::commit (this=0x99724f8, home=..., a=0,
    x=..., i=56, n=1) at gecode/gecode/kernel/brancher-val-sel-commit.hpp:175
#2  0x080774b8 in Gecode::ViewValBrancher<BV::Bit::BitView, 1, unsigned int, 2u>::commit (this=0x9972610, home=..., c=..., b=0)
    at gecode/gecode/kernel/brancher-view-val.hpp:286
#3  0x4003911c in Gecode::Space::_commit (this=0x80b13a0, c=..., a=0) at gecode/kernel/core.cpp:417
#4  0x40046dad in commit (a=<optimized out>, c=..., this=0x80b13a0) at ./gecode/kernel/core.hpp:2786
#5  commit (i=137, s=0x80b13a0, this=0x80cfb88) at ./gecode/search/sequential/path.hh:259
#6  recompute (stat=..., a_d=<optimized out>, d=@0x80cfba8: 3, this=0x80cfb88) at ./gecode/search/sequential/path.hh:325
#7  next (this=0x80cfb44) at ./gecode/search/sequential/dfs.hh:148
#8  Gecode::Search::WorkerToEngine<Gecode::Search::Sequential::DFS>::next (this=0x80cfb40) at ./gecode/search/support.hh:84
#9  0x0804dcda in next (this=<optimized out>) at gecode/gecode/search/dfs.hpp:53
#10 main (argc=4, argv=0xbffff2f4) at src/main.cpp:75

I'm not quite sure how to proceed since the search process is rather difficult
to step through in the debugger and since I'm using the built-in ViewSelNone.

Any suggestions? I can provide code for any relevant methods, but it's not
clear to me which would be actually useful for you guys to see.

System info:
OS: debian linux, kernel 2.6.32.33-kvm-i386-20111128-dirty, 
    running in a VM (KVM or UML, I'm not quite sure)
Gecode version: 4.2.1, built from source
g++ (Debian 4.7.2-5) 4.7.2

Cheers,
Kellen