Search is essential for constraint programming. Search engines
typically combine several features like state restoration for
backtracking, best solution
search, parallelism, or visualization.
In current implementations like Mozart, however, these search engines
are monolithic and hard-wired to one exploration strategy,
severely complicating the implementation of new exploration
strategies and preventing their reuse.
This paper presents the design of a for Mozart,
a program that enables the user to freely combine several orthogonal
aspects of search, resulting in a search engine tailored to the
user's needs. The abstractions developed here support fully
automatic recomputation with last alternative optimization. They
present a clean interface, making the implementation of new
exploration strategies simple. Conservative extensions of the
abstractions are presented that support best solution search and
parallel search as orthogonal modules. IOzSeF, the Interactive Oz
Search Factory, implements these abstractions and is freely
available for download.
© Springer-Verlag, (Lecture Notes in Computer Science)