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 > > > > > > > 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
