Conditional Constraints and Composite Variables with Preferences

We present an extension of the well known Constraint Satisfaction Problem (CSP) framework in order to manage constraint problems in a dynamic environment and when the information corresponding to any possible change is known and available a priori. The new model is called Conditional and Composite CSP (CCCSP) and enables the addition|retraction of problem variables (and their corresponding constraints), during the constraint solving process, via conditional constraints and composite variables. A conditional constraint restricts the participation of a variable in a feasible scenario while a composite variable allows us to express a disjunction of variables where only one will be added to the problem to solve. Using the Allen Interval Algebra and a discrete representation of time, the CCCSP is adapted in order to handle the particular case of numeric and symbolic temporal constraints. Through the C-semiring structure, we show how to integrate preferences into the CCCSP and its temporal variant that we call Temporal CCCSP (or TCCCSP). Finally, we report the results of an extensive experimental study we conducted in order to evaluate the time performance of the complete and incomplete methods, we propose, for solving CCCSPs and TCCCSPs.