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. Gecodes arent. 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
