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).     

Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty

In classical Constraint Satisfaction Problems (CSPs) knowledge is embedded in a set of hard constraints, each one restricting the possible values of a set of variables. However constraints in real world problems are seldom hard, and CSP's are often idealizations that do not account for the preference among feasible solutions. Moreover some constraints may have priority over others. Lastly, constraints may involve uncertain parameters. This paper advocates the use of fuzzy sets and possibility theory as a realistic approach for the representation of these three aspects. Fuzzy constraints encompass both preference relations among possible instantiations and priorities among constraints. In a Fuzzy Constraint Satisfaction Problem (FCSP), a constraint is satisfied to a degree (rather than satisfied or not satisfied) and the acceptability of a potential solution becomes a gradual notion. Even if the FCSP is partially inconsistent, best instantiations are provided owing to the relaxation of some constraints. Fuzzy constraints are thus flexible. CSP notions of consistency and k-consistency can be extended to this framework and the classical algorithms used in CSP resolution (e.g., tree search and filtering) can be adapted without losing much of their efficiency. Most classical theoretical results remain applicable to FCSPs. In the paper, various types of constraints are modelled in the same framework. The handling of uncertain parameters is carried out in the same setting because possibility theory can account for both preference and uncertainty. The presence of uncertain parameters leads to ill-defined CSPs, where the set of constraints which defines the problem is not precisely known.     

Efficient flexible planning via dynamic flexible constraint satisfaction

Recent advances in AI planning have centred upon the reduction of planning to a constraint satisfaction problem (CSP) enabling the application of the efficient search algorithms available in this area. This paper continues this approach, presenting a novel technique which exploits (restriction/relaxation-based) dynamic CSP (rrDCSP) in order to further improve planner performance. Using the standard Graphplan framework, it is shown how significant efficiency gains may be obtained by viewing plan extraction as the solution of a hierarchy of such rrDCSPs. Furthermore, by using flexible constraints as a formal foundation, it is shown how the traditional boolean notion of planning can be extended to incorporate prioritised and preference-based information. Plan extraction in this context is shown to generalise the Boolean rrDCSP approach, being systematically supported by the recently developed solution techniques for dynamic flexible CSPs (DFCSPs). The proposed techniques are evaluated via benchmark boolean problems and a novel flexible benchmark problem. Results obtained are very encouraging.     

Solving constraint satisfaction problems using hybrid evolutionarysearch

We combine the concept of evolutionary search with the systematic search concepts of arc revision and hill climbing to form a hybrid system that quickly finds solutions to static and dynamic constraint satisfaction problems (CSPs). Furthermore, we present the results of two experiments. In the first experiment, we show that our evolutionary hybrid outperforms a well-known hill climber, the iterative descent method (IDM), on a test suite of 750 randomly generated static CSPs. These results show the existence of a “mushy region” which contains a phase transition between CSPs that are based on constraint networks that have one or more solutions and those based on networks that have no solution. In the second experiment, we use a test suite of 250 additional randomly generated CSPs to compare two approaches for solving CSPs. In the first method, all the constraints of a CSP are known by the hybrid at run-time. We refer to this method as the static method for solving CSPs. In the second method, only half of the constraints of a CSPs are known at run-time. Each time that our hybrid system discovers a solution that satisfies all of the constraints of the current network, one additional constraint is added. This process of incrementally adding constraints is continued until all the constraints of a CSP are known by the algorithm or until the maximum number of individuals has been created. We refer to this second method as the dynamic method for solving CSPs. Our results show hybrid evolutionary search performs exceptionally well in the presence of dynamic (incremental) constraints, then also illuminate a potential hazard with solving dynamic CSPs     

Lexicographically-ordered constraint satisfaction problems

We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice.     

Efficient handling of universally quantified inequalities

This paper introduces a new framework for solving quantified constraint satisfaction problems (QCSP) defined by universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and technology. We introduce a generic branch and prune algorithm to tackle these continuous CSPs with parametric constraints, where the pruning and the solution identification processes are dedicated to universally quantified inequalities. Special rules are proposed to handle the parameter domains of the constraints. The originality of our framework lies in the fact that it solves the QCSP as a non-quantified CSP where the quantifiers are handled locally, at the level of each constraint. Experiments show that our algorithm outperforms the state of the art methods based on constraint techniques. This paper is an extended version of a paper published at the SAC 2008 conference [15].     

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we propose model induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generated induced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify three new classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.     

A branch and bound algorithm for numerical Max-CSP

The Constraint Satisfaction Problem (CSP) framework allows users to define problems in a declarative way, quite independently from the solving process. However, when the problem is over-constrained, the answer “no solution” is generally unsatisfactory. A Max-CSP \(\mathcal{P}_m = \langle V, \textbf{D}, C \rangle\) is a triple defining a constraint problem whose solutions maximize the number of satisfied constraints. In this paper, we focus on numerical CSPs, which are defined on real variables represented as floating point intervals and which constraints are numerical relations defined in intension. Solving such a problem (i.e., exactly characterizing its solution set) is generally undecidable and thus consists in providing approximations. We propose a Branch and Bound algorithm that provides under and over approximations of a solution set that maximize the maximum number \({m_{\mathcal P}}\) of satisfied constraints. The technique is applied on three numeric applications and provides promising results.     

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight of satisfied constraints is maximized. We consider this problem and its variant Max AW CSP where the weights are allowed to be both positive and negative, and study how the complexity of the problems depends on the allowed constraint types. We prove that Max AW CSP over an arbitrary finite domain exhibits a dichotomy: it is either polynomial-time solvable or NP-hard. Our proof builds on two results that may be of independent interest: one is that the problem of finding a maximum H-colourable subdigraph in a given digraph is either NP-hard or trivial depending on H, and the other a dichotomy result for Max CSP with a single allowed constraint type.     

一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法.     

Static and dynamic structural symmetry breaking

We reconsider the idea of structural symmetry breaking for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all the compositions of these (unconditional) symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, and yet they are able to remove a super-exponential number of symmetries on both values and variables. Moreover, we compare the search trees under static and dynamic structural symmetry breaking when using fixed variable and value orderings. These results are then generalised to wreath-symmetric CSPs with both variable and value symmetries. We show that there also exists a polynomial-time dominance-detection algorithm for this class of CSPs, as well as a linear-sized set of constraints that breaks these symmetries statically.     

Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

Constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.     

Issues in the performance measurement of constraint-satisfaction techniques

The richness of the constraint satisfaction problem (or CSP) in representing combinatorial search maladies has resulted in a torrent of techniques for efficiently solving them. These techniques have focused on discovering better backtrack points, learning from dead-ends and avoiding repetitious interference, problem reduction method and the use of network heuristics. Much of this research has derived innovative methods for solving the CSP, however, the evaluations of the techniques have remained diverse and in many cases, statistically inaccurate.Another issue with regard to the performance measurement of constraint satisfaction techniques is the inability to model computational constraint processing cost. It is not uncommon to find evaluations that are based on CSPs that differ only on the percentage of constraints and the tightness of each constraint. This may be justifiable if it can be established that they are the only contributing factors of the performance variable. The three aspects mentioned above comprise this paper's main focus points. They come under the general headings of Modelling CSP Difficulty, Modelling Constraint Cost and Elucidating Major Performance Factors respectively. This paper seeks to provide a set of proposals with respect to the above three well-known areas so as collectively to enhance the robustness of evaluations conducted in the field of constraint satisfaction.     

Nogood-FC for solving partitionable constraint satisfaction problems

Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs.     

Structural decompositions for problems with global constraints

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.     

Using Constraint Satisfaction for View Update

View update is the problem of translating update requests against a view into update requests against the base data. In this article, we present a novel approach to generating alternative translations of view updates in relational databases. Using conditional tables to represent relational views, we transform a view update problem into constraint satisfaction problems (CSPs). Solutions to the CSPs correspond to possible translations of the view update. Semantic information to resolve ambiguity can be incrementally added as constraints in the CSPs. The connection between view update and constraint satisfaction makes it possible to apply the rich results of the CSP research to analyze and solve the important problem of view management.     

Relatively quantified constraint satisfaction

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the more general framework of quantified constraint satisfaction, in which variables can be quantified both universally and existentially. We study the relatively quantified constraint satisfaction problem (RQCSP), in which the values for each individual variable can be arbitrarily restricted. We give a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language.     

Dynamic constraint satisfaction problems over models

In early phases of designing complex systems, models are not sufficiently detailed to serve as an input for automated synthesis tools. Instead, a design space is constituted by multiple models representing different valid design candidates. Design space exploration aims at searching through these candidates defined in the design space to find solutions that satisfy the structural and numeric design constraints and provide a balanced choice with respect to various quality metrics. Design space exploration in an model-driven engineering (MDE) context is frequently tackled as specific sort of constraint satisfaction problem (CSP). In CSP, declarative constraints capture restrictions over variables with finite domains where both the number of variables and their domains are required to be a priori finite. However, the existing formulation of constraint satisfaction problems can be too restrictive to capture design space exploration in many MDE applications with complex structural constraints expressed over the underlying models. In this paper, we interpret flexible and dynamic constraint satisfaction problems directly in the context of models. These extensions allow the relaxation of constraints during a solving process and address problems that are subject to change and require incremental re-evaluation. Furthermore, we present our prototype constraint solver for the domain of graph models built upon the Viatra2 model transformation framework and provide an evaluation of its performance with comparison to related tools.     

Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.     

Robustness,stability, recoverability,and reliability in constraint satisfaction problems

Many real-world problems in Artificial Intelligence (AI) as well as in other areas of computer science and engineering can be efficiently modeled and solved using constraint programming techniques. In many real-world scenarios the problem is partially known, imprecise and dynamic such that some effects of actions are undesired and/or several unforeseen incidences or changes can occur. Whereas expressivity, efficiency, and optimality have been the typical goals in the area, there are several issues regarding robustness that have a clear relevance in dynamic Constraint Satisfaction Problems (CSPs). However, there is still no clear and common definition of robustness-related concepts in CSPs. In this paper, we propose two clearly differentiated definitions for robustness and stability in CSP solutions. We also introduce the concepts of recoverability and reliability, which arise in temporal CSPs. All these definitions are based on related well-known concepts, which are addressed in engineering and other related areas.