[gecode-users] Initialization of internal tree nodes in the unary Edge Finding propagator

[Christian Schulte]

Hi,

Maybe we take that offline as the scheduling stuff is not yet final.

Christian

--
Christian Schulte, web.ict.kth.se/~cschulte/



-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Roberto Castañeda
Sent: Friday, September 24, 2010 12:46 PM
To: users at gecode.org
Subject: [gecode-users] Initialization of internal tree nodes in the unary
Edge Finding propagator

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.