[gecode-users] member function branching

[Patrik Haslum]

Hi,

Looking for hints for an easy way to customise the branching strategy in 
a solver implemented using Gecode, I searched through the archive of 
this list and found the MemberFunctionBranch code (thread "staged 
search", from early october this year).

I found this piece of code very helpful in implementing my branching 
strategy. (So many thanks to both the one who asked the original 
question and the one who provided the answer!) Abstracted a bit, what 
I've done is:

In "my space" constructor:

  MemberFunctionBranch<my space>::post(my_branching_function);

in my_branching_function:

  next_var = <some calculations to figure out next branching variable>;
  IntVarArgs va(1);
  va[0] = my_var_array[next_var];
  branch(this, va, ..., ...);
  MemberFunctionBranch<my space>::post(my_branching_function);
  return ES_OK;

That is, the branching function re-installs itself as the next branch 
point after each "real" branching point (on a variable).

However, when used with branch-and-bound search, this gives me incorrect 
results: On one example problem, I get a sequence of solutions with 
decreasing cost, 486, 344, 324, 304, after which it reports that there 
are no more solutions. But if I start the same branch-and-bound search 
with an initial upper bound of, say, 300, it finds a solution with cost 
284 (which is what I think is optimal).

Does anyone know why this happens?

As an additional comment, something I would appreciate in future 
versions of Gecode is some more "helpers" for custom branching, like the 
MemberFunctionBranch. It may be possible to implement any branching 
strategy with the current interface, but it's not exactly easy. Why not 
a branch function/object that takes as argument a vector of constraint 
expressions (the kind that you post by "post(tt(...))", don't remember 
what the type is called) and branches by posting one of them? That would 
make it easy to use a branching such as for example, "x < y" or "y > x", 
which I don't know how to do (simply!) with the current interface.

Regards,

P at trik Haslum