[gecode-users] Efficiently excluding a set of values from the domains of multiple IntVars

[Kish Shen]

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.