Implementation and Applications of Ad Hoc Constraints

Abstract

To successfully solve a combinatorial problem using constraint-based techniques (constraint programming), we need to represent the constraints and model the problem in a way that strong constraint propagation can be efficiently computed; also, we must devise a search strategy that explores the search space as little as possible, taken into account the efficiency trade-offs. This thesis presents the roles of ad hoc constraints in these four issues. In particular, we show how multi-valued decision diagrams can be used to represent constraints, model and solve constraint satisfaction problems efficiently and effectively.