[gecode-users] member function branching

[Mikael Zayenz Lagerkvist]

Hi,

The MemberFunctionBranch that was posted earlier can not be used in
the way that you propose. The problem is in the part:
    next_var = <some calculations to figure out next branching variable>;
Due to batch recomputation, the MemberFunctionBranch must not depend
on the values of the variables, since the space in most cases has not
been propagated yet. For example, changing the c-d-parameter should
give you different results.

While we are aware that some helpers for creating branchings would be
good, we don't know how to implement a good and simple system yet. On
the bright side, while a full custom branching (as in queen-armies.cc
and black-hole.cc) might not be very pretty, they are fairly easy to
write. The main parts are status, description, and commit. The parts
are described below
 - status
    Checks whether there is anything left to do for this branching.
Typically looks for an unassigned variable.
 - description
    Computes the actual branching to be done. How to do the branching
is encoded in a BranchingDesc, and is returned. This description is
often used in another Space than the Space it was constructed in, so
the description can not contain a variable for example, only
unchanging data such as variable-array indices.
 - commit
    Performs alternative number a of a BranchingDesc d. Note that
commit cannot rely on anything about the variables - they may have
fewer values, more values, or even an incomparable set of values to
the values of the variables when the description was computed. This is
due to batch recomputation and/or optimization.


Hope this helps,
Mikael

On Thu, Nov 13, 2008 at 5:05 AM, Patrik Haslum <patrik.haslum at anu.edu.au> wrote:
>
> 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
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/