[gecode-users] Set propagators and modification event delta
Gustavo Gutierrez
gustavo.ggutierrez at gmail.com
Thu Aug 21 04:25:45 CEST 2014
Thanks much for your help!
Regards,
Gustavo
—
Gustavo
On Wed, Aug 20, 2014 at 7:03 PM, Guido Tack <tack at gecode.org> wrote:
> On 21 Aug 2014, at 5:18 am, Gustavo Gutierrez <gustavo.ggutierrez at 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 <cschulte at 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-bounces at gecode.org [mailto:users-bounces at 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 <tack at 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.ggutierrez at 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 at gecode.org
>> > https://www.gecode.org/mailman/listinfo/gecode-users
>>
>>
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140820/bc594027/attachment-0001.html>
More information about the users
mailing list