Composing constraint solvers

Composing constraint solvers based on tree search and constraint propagation through generic iteration leads to efficient and flexible constraint solvers. This was demonstrated using OpenSolver, an abstract branch-and-propagate tree search engine that supports a wide range of relevant solver configurations. We gave an account of the design and implementation, and of many experiments that were performed to evaluate the approach. The efficiency of OpenSolver-based constraint solvers compares well to that of existing solvers, some of which are successful commercial products. Yet, the following combination of features gives OpenSolver some unique advantages over each of the other systems that we considered. • OpenSolver is a branch-and-propagate constraint solving engine, and makes configurable those aspects that are hardwired in many other systems, such as the constraint propagation algorithm and implementation of the data types. Modeling languages can be implemented on top of it, by means of a compilation step. • OpenSolver promotes the composition of complex strategies from atomic solver “building blocks,” implemented as plug-ins. This prevents duplicate solver code, and allows that techniques carry over to other data types and application domains. • While it is a white-box framework from the perspective of writing new plugins for it, OpenSolver aims at black-box composition of solvers. This led to an inherently linguistic approach where solvers are composed through scripts in a simple configuration language. • OpenSolver is designed as a stand-alone application. Compared to libraries for constraint solving, this makes it independent of a particular programming language. Composing constraint solvers around OpenSolver is primarily a matter of exogenous coordination and component-based software engineering. This is opposite to the approach taken by logic programming systems, which provide a full development environment. • Because of the coordination layer mechanism, OpenSolver can be adapted to many different environments, and the solving process can be controlled externally. In particular, it is suited for distributed constraint solving. • In combination with the configuration language, the coordination layer mechanism opens up new possibilities for implementing parallel search, insearch transformation of CSPs and solver configurations, and it allows for checkpoint mechanisms. Thanks to the flexibility of the system, we could further achieve the following results related to the specific research questions addressed in some of the individual chapters. • We demonstrated how a number of techniques that are normally hard-wired in solvers can be realized through composition. • We performed a comparative study of several approaches to implementing arithmetic constraints on variables with integer interval domains. The best performance was observed for decomposition and hierarchical scheduling of the reduction operators. For this approach we characterized in part the effect of constraint propagation. • We demonstrated the technique of constraining special purpose domain types. • We demonstrated that several pruning techniques from various application domains can be expressed and implemented as applications of a generic operator for nested search. • We evaluated a novel time-out mechanism for load balancing in parallel search, and demonstrated that it can lead to efficient and scalable parallel constraint solver