Hello, everyone! I am studying the propagation algorithms for unary resource constraints from Petr Vilím [1], and looking at how they are implemented in Gecode 3.4.0. While looking at the implementation of the Edge Finding algorithm (scheduling/unary/edge-finding.hpp), I have found a discrepancy with respect to Algorithm 2.6 in [1] that I do not really understand: in the Gecode implementation, the internal nodes of the Theta-Lambda tree are not initialized (i.e. assigned values for p, ect, lp, lect computed from the leaves upwards) at the beginning of the algorithm.
I have also checked if this makes any difference on the propagation for the root search node for the example from Figure 2.4. [1]. This is the frequency of execution of each propagator before reaching the fixpoint with the original Gecode Edge Finding algorithm: 6 Detectable Precedences 6 Edge Finding 6 Not-First/Not-Last 3 Overload Checking 3 Subsumed And this is the frequency when I initialized all nodes at the beginning (with time complexity O(n)): 4 Detectable Precedences 4 Edge Finding 4 Not-First/Not-Last 2 Overload Checking 2 Subsumed While the constraint stores in the fixpoint are equal in both cases, the second version (which I believe is what [1] proposes) saves one iteration of the whole family of unary resource propagators. Is there any reason I missed for not initializing the internal nodes of the Theta-Lambda tree? I attach the Figure 2.4. example code. Best regards, Roberto [1] Petr Vilím, Global Constraints in Scheduling, PhD thesis, Charles University, Prague, Czech Republic, 2007.
figure_2_4.cpp
Description: figure_2_4.cpp
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
