Catálogo de publicaciones - libros

A subgraph isomorphism problem consists in deciding if there exists a copy of a pattern graph in a target graph. We introduce in this paper a filtering algorithm dedicated to this problem. The main idea is to label every node with respect to its relationships with other nodes of the graph, and to define a partial order on these labels in order to express compatibility of labels for subgraph isomorphism. This partial order over labels is used to filter domains. Labelings can also be strengthened by adding information from the labels of the neighbors. Such a strengthening can be applied iteratively until a fixpoint is reached. Practical experiments illustrate that our new filtering approach is more effective on difficult instances of scale free graphs than state-of-the-art algorithms and other CP approaches.

Constraints have played a central role in because they capture key substructures of a problem and efficiently exploit them to boost inference. This paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as , and sequencing constraints, such as . In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.

Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a strategy by using the min-domain property [10,4,20,6]. Ordering heuristics have been introduced recently to , for distributed constraints satisfaction () [27]. However, the pioneering study of dynamically ordered ABT, _, has shown that a straightforward implementation of the min-domain heuristic does not produce the expected improvement over a static ordering. The best ordering heuristic for asynchronous backtracking was found to be the heuristic.

The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in _. Agents can be moved to a position that is higher than that of the target of the backtrack ().

Combining the Nogood-triggered heuristic and the min-domain property in this new class of heuristics results in the best performing version of _. The new version of retroactively ordered ABT is faster by a large factor than the best form of ABT.

Defence trees are used to represent attack and defence strategies in security scenarios; the aim in such scenarios is to select the set of countermeasures have to be applied to stop all the vulnerabilities. To represent the preference among the possible countermeasures of a given attack, defence trees are enriched with CP-networks (CP-net for short). However, for complex trees, composing CP-nets could be not always effective. In this paper we overcome these limitations by transforming each CP-net in an (ASO) program. The ASO program, representing the overall scenario, is a special composition of the programs associated to each branch of the defence tree. The best set of countermeasure able to mitigate all the vulnerabilities is then obtained by computing the optimal answer set of the corresponding ASO program.

Preferences and uncertainty are common in many real-life problems. In this paper, we focus on bipolar preferences and on uncertainty modelled via uncontrollable variables. However, some information is provided for such variables, in the form of possibility distributions over their domains. To tackle such problems, we eliminate the uncertain part of the problem, making sure that some desirable properties hold about the robustness of the problem’s solutions and its relationship with their preference. We also define semantics to order the solutions according to different attitudes with respect to the notions of preference and robustness.

When performing interval propagation on integer variables with a large range, phenomena are often observed: it becomes difficult to reach the fixpoint of the propagation. This problem is practically important, as it hinders the use of propagation techniques for problems with large numerical ranges, and notably problems arising in program verification. A number of attempts to cope with this issue have been investigated, yet all of the proposed techniques only guarantee a fast convergence on specific instances. An important question is therefore whether slow convergence is to propagation methods, or whether an improved propagation algorithm may exist that would avoid this problem. This paper proposes the first analysis of the slow convergence problem under the light of complexity results. It answers the question, by a negative result: if we allow propagators that are general enough, computing the fixpoint of constraint propagation is shown to be intractable. . The result holds for the propagators of a basic class of constraints.

In this paper we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.

In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. The most efficient method for solving this problem consists in a search algorithm using, on the one hand, the weak composition closure method as a local propagation method, and on the other hand, a decomposition of the constraints into subrelations of a tractable set. We extend this algorithm with the notion of eligibility and the notion of frozen constraints. The first concept allows to characterise constraints which will not be considered during the search. The second one allows to freeze constraints in order to avoid unnecessary updates.

Various encodings have been proposed to convert Constraint Satisfaction Problems (CSP) into Boolean Satisfiability problems (SAT). Some of them use a logical variable for each element in each domain: among these very successful are the and the encodings.

Other methods, such as the -encoding, use a logarithmic number of logical variables to encode domains. However, they lack the propagation power of the direct and support encodings, so many SAT solvers perform poorly on log-encoded CSPs.

In this paper, we propose a new encoding, called , that combines the log and support encodings. It has a logarithmic number of variables, and uses support clauses to improve propagation. We also extend the encoding using a Gray code. We provide experimental results on Job-Shop scheduling and randomly-generated problems.

We introduce groupoids – generalisations of groups in which not all pairs of elements may be multiplied, or, equivalently, categories in which all morphisms are invertible – as the appropriate algebraic structures for dealing with conditional symmetries in Constraint Satisfaction Problems (CSPs). We formally define the Full Conditional Symmetry Groupoid associated with any CSP, giving bounds for the number of elements that this groupoid can contain. We describe conditions under which a Conditional Symmetry sub-Groupoid forms a group, and, for this case, present an algorithm for breaking all conditional symmetries that arise at a search node. Our algorithm is polynomial-time when there is a corresponding algorithm for the type of group involved. We prove that our algorithm is both sound and complete – neither gaining nor losing solutions.