There is one more thing: when giving the cost for a propagator in Gecode, you give its complexity and an additional hint whether it has a low or high constant factor. This is then rolled into a cost value by the kernel and used for scheduling. So you have an influence by choosing either a high or low constant factor.
And as Guido said, simple set propagators are more costly than simple integer propagators. But many integer propagators _do_ something sophisticated and hence costly: build a graph, etc, Set propagators tend to not do that. One thing that I always wanted to do, but never did is the following: choose a set of benchmarks (must be large) and experimentally determine good cost factors for them. But that would take gazillion years to run. Cheers Christian -- Christian Schulte, Professor of Computer Science, KTH, www.ict.kth.se/~cschulte/ From: Gustavo Gutierrez [mailto:gustavo.ggutier...@gmail.com] Sent: Thursday, August 21, 2014 4:26 AM To: Guido Tack Cc: Christian Schulte; gecode list Subject: Re: [gecode-users] Set propagators and modification event delta Thanks much for your help! Regards, Gustavo — Gustavo On Wed, Aug 20, 2014 at 7:03 PM, Guido Tack <t...@gecode.org> wrote: On 21 Aug 2014, at 5:18 am, Gustavo Gutierrez <gustavo.ggutier...@gmail.com> wrote: Hi Christian, Thanks a lot for the paper reference. It was indeed the kind of experimentation I was looking for. I have two further questions, the first of them I probably know the answer already but I just one confirmation. 1) Suppose you have two solvers for the same csp that only differ in the first one not using any optimization like modification events or dynamic scheduling of propagators. The second one uses the optimization so described in the paper you pointed out. Given that both solvers are applied to the same problem instance the search trees must be the same, right?. My guess here is founded on the fact that we talk about an optimization but in both cases every solver will compute the same fix point for every node in the search tree. That's correct (as long as the propagators are monotonic, which most of them are). 2) Let suppose a solver that uses both finite domains and finite sets. Let me suppose also for this question that propagating on set variables is more expensive that on integer variables (probably due to the domain representation ). Now, if there are two propagators in the solver that report the same cost, for instance binary::high does the geode kernel make any distinction between them when they are going to be executed?. No, the variable type does not have an influence on the scheduling. You'd have to give your set propagators a higher cost if you want them to be scheduled after the integer propagators. My last question is derived from the following use case. How do I force the execution of all propagators on set variables after all the propagators on finite variables have been executed. As I said, give them higher cost. But you probably won't be able to guarantee execution order (and a propagator for x subset y might be a lot cheaper than alldifferent on an array of integer variables!). Cheers, Guido Regards, Gustavo — Gustavo On Wed, Aug 20, 2014 at 1:12 PM, Christian Schulte <cschu...@kth.se> wrote: We have measured the impact for integer variables even with different modification events. You can check it here: <http://www.gecode.org/~schulte/paper.html?id=SchulteStuckey:TOPLAS:2008> http://www.gecode.org/~schulte/paper.html?id=SchulteStuckey:TOPLAS:2008 There might be more to gain for set variables, but I am only guessing here. Cheers Christian -- Christian Schulte, KTH, web.it.kth.se/~cschulte/ From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Gustavo Gutierrez Sent: Wednesday, August 20, 2014 07:26 PM To: Guido Tack Cc: gecode list Subject: Re: [gecode-users] Set propagators and modification event delta Hi Guido, Thanks for the answer. Did you measured the impact of using modification events in the propagate method versus normal implementations of the propagators? What I mean by normal implementations is suppose you implement the pruning rules without taking into account what have changed since the last time. That will of course maintain the correctness but you will end up applying unnecessary operations. Are the two variants significantly different in the case of set variables? I'm asking this because using modifications events lead to more involved code and is very easy to get it wrong. But on the other hand, is something I will keep doing for performance reasons. Regards, Gustavo — Gustavo On Wed, Aug 20, 2014 at 3:27 AM, Guido Tack <t...@gecode.org> wrote: Hi Gustavo, modification events are really sets of modifications, e.g. if you have only a lower bound modification the event is ME_SET_GLB, for only upper bound it's ME_SET_LUB, but if both have been modified you get ME_SET_BB. You guessed correctly: The testSetEventLB function returns true if the argument event contains a lower bound modification (so it could be ME_SET_GLB, ME_SET_BB, ME_SET_CGLB or ME_SET_CBB). The versions with multiple arguments test whether any of them contains a lower bound modification (the implementation computes the union of the events and then does the check). Cheers, Guido On 20 Aug 2014, at 12:33 am, Gustavo Gutierrez <gustavo.ggutier...@gmail.com> wrote: > Dear all, > > I am trying to write a propagator and I really would like to take advantage > of the modification event information offered by the geocode kernel in the > respective argument to the propagate method. To that end, I am looking at set > propagators as an example. In concrete I am looking at the code of the > intersection propagator in inter.hpp. > > That implementation calls testSetEventLB defined in common.hpp. My question > is concrete: does this function returns true when the modification event > passed as parameter signals a modification of the lower bound?. My intuition > from its definition and the internal functions it uses tell me so but I would > like to corroborate it with you. > > There are other testSetEvent* that take a different number of arguments (all > of them being modification events). For example, testSetEventLB with two > arguments. Does this one returns true if any of the two events imply > modification to the lower bounds? > > Best regards, > -- > Gustavo Gutierrez > _______________________________________________ > Gecode users mailing list > users@gecode.org > https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
