Conditional and composite temporal CSPs

Constraint Satisfaction Problems (CSPs) have been widely used to solve combinatorial problems. In order to deal with dynamic CSPs where the information regarding any possible change is known a priori and can thus be enumerated beforehand, conditional constraints and composite variables have been studied in the past decade. Indeed, these two concepts allow the addition of variables and their related constraints in a dynamic manner during the resolution process. More precisely, 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. In order to deal with a wide variety of real life applications under temporal constraints, we present in this paper a unique temporal CSP framework including numeric and symbolic temporal information, conditional constraints and composite variables. We call this model, a Conditional and Composite Temporal CSP (or CCTCSP). To solve the CCTCSP we propose two methods respectively based on Stochastic Local Search (SLS) and constraint propagation. In order to assess the efficiency in time of the solving methods we propose, experimental tests have been conducted on randomly generated CCTCSPs. The results demonstrate the superiority of a variant of the Maintaining Arc Consistency (MAC) technique (that we call MAX+) over the other constraint propagation strategies, Forward Checking (FC) and its variants, for both consistent and inconsistent problems. It has also been shown that, in the case of consistent problems, MAC+ outperforms the SLS method Min Conflict Random Walk (MCRW) for highly constrained CCTCSPs while both methods have comparable time performance for under and middle constrained problems. MCRW is, however, the method of choice for highly constrained CCTCSPs if we decide to trade search time for the quality of the solution returned (number of solved constraints).     

Managing dynamic CSPs with preferences

We present a new framework, managing Constraint Satisfaction Problems (CSPs) with preferences in a dynamic environment. Unlike the existing CSP models managing one form of preferences, ours supports four types, namely: unary and binary constraint preferences, composite preferences and conditional preferences. This offers more expressive power in representing a wide variety of dynamic constraint applications under preferences and where the possible changes are known and available a priori. Conditional preferences allow some preference functions to be added dynamically to the problem, during the resolution process, if a given condition on some variables is true. A composite preference is a higher level of preference among the choices of a composite variable. Composite variables are variables whose possible values are CSP variables. In other words, this allows us to represent disjunctive CSP variables. The preferences are viewed as a set of soft constraints using the fuzzy CSP framework. Solving constraint problems with preferences consists in finding a solution satisfying all the constraints while optimizing the global preference value. This is handled by four variants of the branch and bound algorithm, we propose in this paper, and where constraint propagation is used to improve the time efficiency in practice. In order to evaluate and compare the performance of these four strategies, we conducted an experimental study on randomly generated dynamic CSPs with quantitative preferences. The results are reported and discussed in the paper.