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

[Guido Tack]

Hi Kish,

I think the main difference will be the domain representation.  Gecode's list-of-ranges representation is inherently less efficient for this type of operation than a bitset.  The best option is of course to create the variables with the right domain in the first place.

There was a small bug in the reified dom constraints in Gecode, which didn't update the domain immediately if the control variable was assigned, but posted propagators instead.  This was easy to fix (it's in the svn trunk now), but in my experiments only accounts for at most 25% overhead (tested with 50000 variables, domain 1..50000, and excluding a random set of 1000 integers from the domains).

I don't think a reified dom for IntVarArgs would be very useful.  If you think it's useful for the eclipse interface, you could simply add that constraint to the native part of the interface (it wouldn't make the execution more efficient, but you'd only have to store one constraint for the backtracking).

Cheers,
Guido

On 7 Nov 2011, at 20:55, Kish Shen wrote:

> 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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/