Hi,
A user who is testing the ECLiPSe Gecode Interface reports an issue he
is having with trying to convert his application from using ECLiPSe's
native solver:
He needs to exclude the same set of values from the domains of a set of
variables. With ECLiPSe's native ic solver, he is doing this with a
primitive which exclude one value from one variable, so he has an outer
loop that loops through the variables, and then for each variable, each
value is excluded:
foreach(V, Vars) do
foreach(Val, Values) do exclude(Val, V)
where exclude removes Val from variable V's domain.
When this code was used in the Gecode interface, the execution time was
about 15 times slower than when running with ic.
In the Gecode interface, the exclude is implemented using a reified
dom() constraint, i.e. something like:
dom(home, V, Val, 0)
Part of the reason for this difference is the removal of one element at
a time. In ic, interer domains are represented as bitmaps, so removing
one value at a time is quite efficient, it is simply a bit operation.
I assume this is not the case with Gecode?
As a way to exclude all the values at the same time, he used reified dom
constraint directly, i.e. something like:
dom(V, Values, 0);
this is faster, but is still 5 times slower than the original code in
ic, and about 20% slower than the equivalent ic code (i.e. also using
reified domain constraint).
Some of the remaining difference is probably caused by the overheads the
Gecode interface needs for allowing recomputation/cloning -- posting of
constraints need to be remembered so that they can be recomputed if
needed. So it should be much more efficient if the set of values can be
excluded from all the variables at once, i.e. something like:
dom(Vars, Values, 0)
however, the refieid domain constraint supports only IntVar, and not
IntVarArgs (unlike the non-reified versions of the constraint).
ECLiPSe also does not support reified domain constraint on multiple
variables (nor the exclusion of a single value from multiple variables,
which is why my user has a loop through the variables). Is there any
strong reason for this restriction, or is it because it is unlikely that
you want to reify the domain of a set of variables in the same way?
Is there a more efficient/direct way in Gecode of excluding one value or
a set of values from the domain of one (or multiple) variables? I am
using reified domain constraint because I could not find any more direct
way of doing this?
Thanks and cheers,
Kish
--
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
