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, [EMAIL PROTECTED] Haslum _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
