On Mon, Apr 4, 2011 at 4:50 PM, Tyrel Russell <[email protected]>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/
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
