[gecode-users] Set propagators and modification event delta

Thu Aug 21 10:06:47 CEST 2014

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.ggutierrez at 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 <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> 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/20140821/88236033/attachment.html>