Hi,

Is there a way to determine the number of propagators in a space? I noticed that we don't provide a way to do this in gfd (ECLiPSe's Gecode interface). This is mostly because gfd's API is based largely on ECLiPSe's native finite domain solver (ic), and ic does not need to provide this, as the number of propagators (delayed goals) can be found using existing ECLiPSe's built-ins.

If a gfd program finishes without some propagators remaining, I assume this is equivalent to an ic program floundering, which is indicated by the presence of any delayed goals. e.g. for the following ic program:

[eclipse 3]: [A,B] :: 1..10, ic:min([A,B], M).

A = A{1 .. 10}
B = B{1 .. 10}
M = M{1 .. 10}


Delayed goals:
        ic_constraints : min2([A{1 .. 10}, B{1 .. 10}], M{1 .. 10})
Yes (0.00s cpu)

The min constraint remain when the program finished.

So I am thinking of providing a function in gfd to obtain the number of propagators, to allow the user to determine if floundering has occurred. It is also a useful measure of how big the problem is (along with the number of variables, which is readily available).

However, trying the min constraint, it seems that the propagator can remain even after the constraint is satisfied, e.g. the following gfd program (i.e. Gecode is used):

?- A :: 1 .. 20, gfd : min([100, A], M), get_constraints_number(M, D).
A = A{[1 .. 20]}
M = M{[1 .. 20]}
D = 1

(this is in ECLiPSe syntax, but I hope it is simple enough to understand: get_constraints_number/2 obtain the degree for the IntVar represented by M)

This shows that the variable M (and I also checked A, not shown here) still have a propagator attached to it even though the min constraint is satiisfied -- I assume this is the propagator for min that is still attached to the variables?

For comparison, for the equiivalent ic program, no delay goals remain, and the degree for M (obtained using delay_goals_number for ic) is 0:

[eclipse 3]: A :: 1..10, ic: min([A,100], M), ic: delayed_goals_number(M, D).

A = A{1 .. 10}
M = A{1 .. 10}
D = 0
Yes (0.00s cpu)

Is an alternative method needed to determine if floundering has occurred for a gfd program?

Thanks and cheers,

Kish



_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users

Reply via email to