[gecode-users] Schedule Branching Recommendations
Filip Konvička
filip.konvicka at logis.cz
Mon Aug 27 17:54:34 CEST 2007
Hi Christian,
> Please do not hesitate to ask more questions of that sort! Do you consider
> to only do branching or also propagation? Because there is a very
> interesting issue for edge-finding/first-last: both propagation and
> branching should share the same data structures to maintain their
> information for efficiency. Support for sharing state among several
> propagators/branching is on our todo list for a long time but we decided to
> only do it when we implement exactly what you are now appareantly trying to
> do...
>
I am in a similar situation now. Could you please explain why (if this
is the case indeed) is it not possible to just share the data in some
raw data structure inside the Space? I mean, in the above mentioned
case, propagation computes some information that can be re-used in the
branching. I was under the impression that the following might work in
similar cases:
- During propagation, store (overwrite) some "raw" data in the Space
instance (I know, this is not exactly a good architecture design...)
- As soon as the Space is stable, the system looks for active
branchings, asking for alternatives
- The branching might access the data now, knowing that it is the result
of the last propagation (which led to the fixpoint), and return some
alternatives
The thing I'm not sure about is whether there must always be a
propagation step after recomputation. In case that not, the branching
should have the possibility to compute the data from scratch, using only
the variables' domains (in this case, copying the space should
invalidate the data to make sure it is recomputed).
The reason I believe this could work is that the shared information is
after all just some kind of cache which reflects the current domains.
Thanks for any comments,
Filip
More information about the gecode-users
mailing list