Hi Christian, Awesome! I changed the variable domains to no longer being from MIN_INT to MAX_INT and the difference in time and number of propagators just dissapear.
Really, thank you very much for your reply! Best regards, Nacho 2013/1/9 Christian Schulte <[email protected]> > Hi,**** > > ** ** > > Just two things completely off my head:**** > > **- **How does your search control recomputation? Gecode is quite > clever, in particular during BAB.**** > > **- **I saw that your variable domains are always from MIN_INT to > MAX_INT. Gecode’s aren’t. This makes quite some difference for Golomb. > Check the MPG case study on Golomb.**** > > ** ** > > Best**** > > Christian**** > > ** ** > > --**** > > Christian Schulte, www.ict.kth.se/~cschulte/**** > > ** ** > > *From:* [email protected] [mailto:[email protected]] *On > Behalf Of *Ignacio Castiñeiras > *Sent:* Wednesday, January 09, 2013 6:13 PM > *To:* [email protected] > *Subject:* [gecode-users] About the different performance of two > "apparently similar" Gecode models**** > > ** ** > > Hi all, **** > > We are obtaining a different performance in two “apparently similar” > Gecode models, and after performing some test we are blocked in finding out > where this different performance comes from. **** > > ** ** > > *CONTEXT:* > > We are performing a modelling and solving comparison of the Golomb Ruler > problem between Gecode and our Constraint Functional Logic Programming > system TOY(FDg) (which uses Gecode for finite domain constraint solving). > Our hypothesis is that, being Golomb an optimization combinatorial problem, > as soon as it scales, the time spent on search will be almost the 100% of > the total elapsed time (making the inherent surcharge of interfacing > TOY(FDg) to Gecode nearly negligible). **** > > ** ** > > Unfortunately (at least for us J) this does not hold. For example, > whereas for Golomb-11 the Gocode model spends 28sec, the TOY(FDg) model > spends 42sec (a 50% of time more). This difference directly comes from the > time they spent on the search, which is strange, as both models are using > the *same formulation* (in the sense of a same number of variables with > same domain, a same set of constraints and a same search strategy). Of > course the resulting Gecode code of our TOY(FDg) interfaced model results > to be less natural than the one obtained when modelling directly over > Gecode (in the sense of having to use a single variable vector and devoted > predicates for adding each new variable and constraint arising in the > TOY(FDg) goal, as some of its drawbacks). **** > > ** ** > > To find out the reason of such this difference we have performed some > tests, which I describe to you (all the files I talk about are attached to > this email). We are using Gecode 3.7.3 with Visual Studio 2008.**** > > ** ** > > *TEST 1.* > > The test uses:**** > > **- **golomb_5_gist_natural.cpp (model using Gecode directly).**** > > **- **golomb_5_gist_natural.res (log of the results from running the > model). **** > > **- **golomb_5_gist_natural.pdf (gist tree obtained by running the > model). **** > > ** ** > > **- **golomb_5_gist_interfaced.cpp (simulation of the resulting > Gecode model obtained from TOY(FDg)).**** > > **- **golomb_5_gist_interfaced.res (log of the results from running > the model).**** > > **- **golomb_5_gist_interfaced.pdf (gist tree obtained by running > the model). **** > > ** ** > > Both models solve Golomb-5, which contain: **** > > **- **Variables: *m[0,m0,m1,m2,m3]*; * > d[d0,d1,d2,d3,d4,d5,d6,d7,d8,d9]*. **** > > **- **Constraints: *m[i]* < *m[i+1]*; *d* represents the pairwise > differences *m*; all_different(*d*); *d[0]* < *d[last]*. **** > > **- **Search: Label *m* in textual order, minimizing *m[last]***** > > ** ** > > Conclusions: **** > > 1. The *pdf* files show that the Gist tree of the Gecode and TOY(FDg) > models are exactly the same. **** > 2. The *res* files show that the propagation is the same in almost of > nodes, *but not in the node remarked in grey in the pdf files*. For > this node Gecode makes m = {0, 1, 6, *8,* 10} and d = {1, 6, *8,* 10, > *[5..6], > [6..7],* 9, 2, 4, 3} (lines 73-76 of golomb_5_gist_natural.res), but > TOY(FDg) makes varsSearch = {1, 6, *7,* 10, 1, 6, *7,* 10, *5, 6,* 9, > 2, 4, 3} (lines 60-62 of golomb_5_gist_interfaced.res). As it is seen in > the gist trees, both systems fail in this node, but TOY(FDg) has to do more > work to discover it). **** > > ** ** > > *TEST 2.* > > The test uses:**** > > **- **golomb_5_bab_natural.cpp (model using Gecode directly).**** > > **- **golomb_5_bab_natural.res (log of the results from running the > model). **** > > ** ** > > **- **golomb_5_bab_interfaced.cpp (simulation of the resulting > Gecode model obtained from TOY(FDg)).**** > > **- **golomb_5_bab_interfaced.res (log of the results from running > the model).**** > > ** ** > > Both models use a search engine (for obtaining statistics of the search) > and the user-defined constraint “checkwhenpruned”, which prints in the log > each modification in the domain of the variables. With that we can control > how the domains of the variables evolve during the search. **** > > ** ** > > Conclusions: **** > > 1. The res files show that both models explore 19 nodes, with 8 fails. > However, whereas the number of propagators in Gecode is 542, for TOY(FDg) > is 544 (possibly the two extra propagators of node remarked in grey in the > pdf files). **** > 2. The res files show that there also two more kind of differences in > the propagation of Gecode and TOY(FDg). Lets focus in the lines 66-83 of > golomb_5_bab_natural.res and the lines 71-89 of > golomb_5_bab_interfaced.res. They represent the propagation performed in > the node remarked in yellow in the pdf files (initial state m = {0, 1, > [3..11], [6..13], [10..15]} and d = {1, [3..11], [6..13], [10..15], > [2..10], [5..12], [9..14], [2..10], [3..12], [2..9]} à final state m = > {0, 1, 3, [7..11], [11..15]} and d = {1, 3, [7..11], [11..15], 2, [6..10], > [10..14], [4..8], [8..12], [4..8]}, thus affecting to *all the > variables*): **** > > **2.1. **The order in which the variables see their domain pruned in > different in Gecode and TOY(FDg), which could come from a different order > in which the constraints are being propagated. **** > > **2.2. **The number of prunnings is different. For example, *in Gecode > there are 18 variable notifications, but in TOY(FDg) there are 19 (the > pruning d[5] = [6..12] appears in TOY(FDg) but not in Gecode*. As it is > seen in the gist trees, both systems success in propagation of this node, > but TOY(FDg) has to do more work to discover it).**** > > ** ** > > *TEST 3.* > > The test uses:**** > > **- **golomb_11_bab_natural.cpp (model using Gecode directly).**** > > **- **golomb_11_bab_natural.res (log of the results from running the > model). **** > > ** ** > > **- **golomb_11_bab_interfaced.cpp (simulation of the resulting > Gecode model obtained from TOY(FDg)).**** > > **- **golomb_11_bab_interfaced.res (log of the results from running > the model).**** > > ** ** > > Both models use the computer clock to measure the elapsed time in running > the problem.**** > > ** ** > > Conclusions: **** > > 1. Again, both models explore the same search tree (2968201 nodes and > 1484086 fails). But, again, the number of propagators is different > (320150379 for Gecode and 295041321 for TOY(FDg)). Interestingly, for > Golomb-11 is Gecode the one that has (much) more propagators. For Golomb-5 > it was TOY(FDg) the one that had (just) two more propagators). **** > 2. Regarding the elapsed time for the search, Gecode (28sec) clearly > outperforms TOY(FDg) (42sec). **** > > ** ** > > *WE NEED HELP:* > > 1. Do you think that the big performance difference of Test3 is > because of the reasons we have found in Test1 and Test2 (where TOY(FDg) > always has to work more than Gecode for obtaining the same propagation > results)? **** > 2. If you think this is not the case, do you have any insight of where > does the performance difference come from? **** > > ** ** > > Thank you very much in advance for spend your time reading this (so long) > email and helping us. **** > > ** ** > > Best regards, **** > > Nacho Castiñeiras **** > > ** ** > > ** ** >
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
