Conditional and composite (temporal) CSP

We propose the Conditional and Composite Constraint Satisfaction Problem (CCCSP) model, a unique framework to efficiently manage dynamic CSPs where dynamic sets of variables and constraints are known under predefined conditions. Two resolution techniques for solving CCCSPs: (1) complete methods based on constraint propagations and (2) incomplete methods based on Stochastic Local Search (SLS), have been developed. The CCCSP framework is augmented to encode numeric and symbolic temporal constraints. The new temporal model is called Conditional and Composite Temporal Constraint Satisfaction Problem (CCTCSP). In addition, the CCCSP resolution methods have been adapted for solving CCTCSPs. In the case of searching for the preferred solution according to a given objective function, preferences defined at different levels of CCCSPs and CCTCSPs indicate degrees of satisfaction and are treated as soft constraints. In order to handle these preferences, the CCCSP and the CCTCSP frameworks are extended with the c-semiring, and the complete solving methods are modified following the Branch and Bound technique. CCCSPs and CCTCSPs with preferences can be applied to applications such as configuration problems, planning and scheduling problems, software designs and expert systems. The proposed algorithms are compared using an extensive experimental study over randomly generated problems. The experimental results demonstrate that in the case of hard problems (i.e., middle constrained and highly dynamic structured instances), our complete solving methods with the advanced constraint propagation techniques outperform the general ones while obtaining the same results. The results also show that, the incomplete methods using SLS techniques are faster than the complete ones in the case of hard problems. These SLS techniques are relevant in case we want to trade the quality of solutions for the time efficiency.