Ad-hoc global constraints for life

Abstract

Still-life is a challenging problem for CP techniques. We show how to use the global case constraint to construct ad-hoc constraints which can provide stronger propagation than existing CP models. We also demonstrate how to use BDDs to construct good representations for the case constraint which is critical for efficiency. Our results seem comparable to hybrid CP/IP models even though we are only using propagation albeit on ad-hoc global constraints. This is rather promising since it shows the potential of ad-hoc global constraints to do better than IP global constraints. © Springer-Verlag Berlin Heidelberg 2005.