Daniel Sabin, Eugene C. Freuder
Selecting and arranging parts is the core of a configuration task. The validity of a configuration is defined in terms of constraints. Highly declarative, domain independent and simple to use, the constraint satisfaction problem (CSP) paradigm offers an adequate framework for this task. However, the basic paradigm is not powerful enough to capture or to take advantage of essential as-pects of configuration, such as the unknown a priori number of constituent parts of a system or the inherent internal structure of these parts. Although notable effort has been spent on extending the basic paradigm to accommodate these issues, we still lack a comprehensive formalism for configuration. This paper presents the main ideas behind a general constraint-based model of configuration tasks represented as a new class of nonstandard constraint satisfaction problems, called composite CSP. Composite CSP unifies several CSP extensions, providing a more comprehensive and efficient basis for formulating and solving configuration problems.