[gecode-users] Singleton Arc Consistency Preprocessing

[Mikael Zayenz Lagerkvist]

On Mon, Apr 4, 2011 at 4:50 PM, Tyrel Russell <tcrussel at cs.uwaterloo.ca>wrote:

> Hi,
>
> Is there a preferred method for applying singleton arc consistency
> preprocessing in Gecode?
>
> The idea that I was considering was to fix each variable value pair and
> determine if a nogood is generated by applying arc consistency with the
> variable-value fixed.  If so, add this nogood to a set of stored nogoods and
> enforce the new set of constraints, iterate through this process until no
> further nogoods are found.
>
> There seem to be two problems with this approach.  First, it seems to be
> necessary to only add constraints in the constructor of a Space object or
> during search which means generating a specific constructor for this
> purpose.  Is there a better way to add constraints to a Space object on the
> fly?  Second, there is an issue of efficiency.  There would a large number
> of calls to my hypothetical constructor which may not be efficient.
>
> I know that singleton arc consistency preprocessing was removed from Gecode
> several versions ago.  Was this because it was too expensive to be
> effective?
>


The reason we removed SAC pre-processing was
 a) it was seldom effective at all for our examples (efficiency was ok)
 b) The implementation was ugly. SAC requires the set of variables to be
know, and the way that was done was not good nor maintainable.

That being said, it is actually quite easy to implement SAC pre-processing
for any particular problem. First, note that the reason constraints are
added in the constructor is simply because it is a convenient way of
structuring code, constraints can be added to a Space at any time. What you
need to do is to first construct your problem instance. Then, make a clone
of your problem for each literal that you want to test. If assigning that
literal in the newly created clone makes the Space failed, then you can
remove it in your original copy. Delete your clone, and start over for your
next literal.

Hope this helps,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110404/c3489a27/attachment.htm>