For the study and the solving of NP-hard problems, the concept of tree decomposition is nowadays a major topic in Computer Science, in Artificial Intelligence and particularly in Constraint Programming. It appears as a promising field for the theoretical study of numerous graphical models like Bayesian Networks or (Weighted) Constraint Networks, since it can ensure, under some hypothesis, the existence of polynomial time algorithms. This concept is also used in a wide range of applications. Recently, a real improvement in the practical computation of optimal tree decompositions has been observed, allowing new promising applications of this concept in real applications. In this paper, we first aim to analyze the real relevance of such optimal decompositions. We first set that a larger set of instances are now optimally decomposable in practice but using these algorithms on a practical level still constitutes a real difficulty. In a second time, we assess the impact of such optimal decompositions for solving these instances and note a discrepancy between the empirical results and what is expected from the complexity analysis. Finally, we discuss of the next investigations which are needed on this topic.

This paper presents an algorithm which solves the multiobjective shortest path problem in a time-dependent graph, taking advantage of the specificities of the weather routing problem. Multicriteria shortest path problems are widely studied in the literature, as well as monocriteria shortest path problems in time-dependent graphs. Their solving has numerous applications, especially in the transportation field. However, the combination of both these issues is not studied as much as each one separately. In this paper, we study the weather routing problem for cargo ships, which involves optimizing the ship routes following realtime weather information. For this problem, the arc weights on the graph have a low dispersion around their average value. We propose an extension of an algorithm (NAMOA*) taking advantage of this property. We study the validity of this new algorithm and explain why it solves efficiently the weather routing problem. Experiments done using real weather data corroborates the algorithm efficiency.

When solving weighted constraint satisfaction problems, methods based on tree-decompositions constitute an interesting approach depending on the nature of the considered instances. The exploited decompositions often aim to reduce the maximal size of the clusters, which is known as the width of the decomposition. Indeed, the interest of this parameter is related to its importance with respect to the theoretical complexity of these methods. However, its practical interest for the solving of instances remains limited if we consider its multiple drawbacks, notably due to the restrictions imposed on the freedom of the variable ordering heuristic. So, we first propose to exploit new decompositions for solving the constraint optimization problem. These decompositions aim to take into account criteria allowing to increase the solving efficiency. Secondly, we propose to use these decompositions in a more dynamic manner in the sense that the solving of a subproblem would be based on the decomposition, totally or locally, only when it seems to be useful. The performed experiments show the practical interest of these new decompositions and the benefit of their dynamic exploitation.

The problem of counting solutions in CSP, called #CSP, is an extremely difficult problem that has many applications in Artificial Intelligence. This problem can be addressed by exact methods, but more classically it is solved by approximate methods. Here, we focus primarily on the exact counting. We show how it is possible to improve the methods based on structural decomposition by offering to enhance the search for a new solution which is a critical step for counting, particularly for such methods. Moreover, if the resources in time or in space are insufficient, we show that our approach is still able to provide a lower bound of the result. Experiments on CSP benchmarks show the practical advantage of our approach w.r.t. the best methods of the literature.

Tractable classes constitute an important issue in Artificial Intelligence to define new islands of tractability for reasoning or problem solving. In the area of constraint networks, numerous tractable classes have been defined, and recently, the Broken Triangle Property (BTP) has been shown as one of the most important of them, this class including several classes previously defined. In this paper, we propose a new class called ETP for Extendable-Triple Property, which generalizes BTP, by including it. Combined with the verification of the Strong-Path-Consistency, ETP is shown to be a new tractable class. Moreover, this class inherits some desirable properties of BTP including the fact that the instances of this class can be solved thanks to usual algorithms (such as MAC or RFL) used in most solvers. We give the theoretical material about this new class and we present an experimental study which shows that from a practical viewpoint, it seems more usable in practice than BTP.

Depending on the nature of CSP instances to consider, the decomposition methods offer an approach often efficient for the solving, the counting of solutions or the optimization. So, the community has focused a large part of its efforts on the design of algorithms aiming to find the best decompositions, i.e. ones which minimize the width of the decomposition, the fundamental parameter in terms of theoretical complexity. In this frame, the heuristic Min-Fill constitutes the reference method. In this paper, we introduce an algorithmic framework for network decomposition aiming to improve Min-Fill. It computes tree-decompositions based on a traversal of the graph using properties related to separators and their associated connected components. Its time complexity is lower than the one of Min-Fill. Moreover, it permits the implementation of several heuristics which can guide the decomposition over several criteria like the size of the clusters, the size of the separators, the connectivity of the clusters, which are particularly relevant to improve the efficiency of the solving by decomposition methods. Experiments assess this new approach and demonstrate its practical advantages for decomposing and solving constraint networks.

From a theoretical viewpoint, the (tree-)decomposition methods offer a good approach when the (tree)-width of constraint networks (CSPs) is small. In this case, they have often shown their practical interest. However, sometimes, a bad choice for the root cluster (a tree-decomposition is a tree of clusters) may drastically degrade the performance of the solving.

Tractable classes constitute an important issue in CP, at least from a theoretical viewpoint. But they are not actually used in practice. Either their treatment is too costly for time complexity or, even if there exist efficient algorithms to manage them, they do not appear in the real problems. We propose here to address this issue thanks to the notion of hidden tractable classes. Such classes are based on a known tractable class C, and a transformation t, and are defined by sets of instances P such that their transformation using t is in C, that is t (P) in C. We propose a general framework to study such notions. After, we focus our study on the tractable class BTP, and several transformations which are the filterings classically used in CP. We show then that the use of filterings allows sometimes to highlight the occurrence of BTP in the benchmarks generally considered for solver comparisons, i.e. That BTP is sometimes "hidden" in the benchmarks. Thus, this approach allows to extend the set of known tractable classes.

Find new islands of tractability, that is classes of CSPs for which polytime algorithms exist, is a fundamental task in the study of constraint satisfaction problems. The concept of hybrid tractable class, which allows to deal simultaneously with the restrictions of languages and, for example, the satisfaction of structural properties, is an approach which has already shown its interest in this domain. Here we study a hybrid class for non-binary CSPs. With this aim in view, we consider the tractable class BTP introduced in [1].While this class has been defined for binary CSPs, the authors have suggested to extend it to CSPs with constraints of arbitrary arities, using the dual representation of such CSPs. We develop this idea by proposing a new definition without exploiting the dual representation, but using a semantic property associated to the compatibility relations of the constraints. This class, called DBTP for Dual BTP, is firstly shown to be tractable. Then it is compared to some known classes. In particular, we prove that DBTP is incomparable with BTP and that it includes some well known classes of CSPs such as beta-acyclic CSPs.

In this paper, we introduce a new partial consistency for constraint networks which is called Structural Consistency of level w and is denoted w-SC consistency. This consistency is based on a new approach. While conventional consistencies generally rely on local properties extended to the entire network, this new partial consistency considers global consistency on subproblems. These subproblems are defined by partial constraint graphs whose tree-width is bounded by a constant w. We introduce a filtering algorithm which achieves w-SC consistency. We also analyze w-SC filtering w.r.t. other classical local consistencies to show that this consistency is generally incomparable although this consistency can be regarded as a special case of inverse consistency. Finally, we present experimental results to assess the usefulness of this approach. We show that w-SC is a significantly more powerful level of filtering and more effective w.r.t. the runtime than SAC. We also show that w-SC is a complementary approach to AC or SAC. So we can offer a combination of filterings, whose power is greater than w-SC or SAC.

In this paper, we consider theoretical and practicalmethods based on decompositions of constraint networks. We exploit the fact that decomposition-based methods can be used considering two steps. The first step is related to the (hyper)graphical decomposition (e.g. Tree-Decomposition [16] or Hypertree-Decomposition [7]) while the second step exploits the decomposition to solve the CSPs. Thanks to this approach, we define then hybrid methods which can be optimal from a theoretical viewpoint while being efficient in practice. The complexity analysis of these combined methods allows us to give a more detailed presentation of the Constraint Tractability Hierarchy introduced in [7]. Finally, we justify our approach with experimental results.

In this paper, a new evaluation of the complexity of Forward Checking for solving non-binary CSPs with finite domains is proposed. Unlike what is done usually, it does not consider the size of domains, but the size of the relations associated to the constraints. It may lead sometimes to define better complexity bounds. By using this first result, we show that the tractability hierarchy proposed in [6] which compares different methods based on a decomposition of constraintnetworks can be seen from a new viewpoint.

This paper deals with the problem of solving efficiently structured COPs (Constraints Optimization Problems). The formalism based on COPs allows to represent numerous real-life problems defined using constraints and to manage preferences and soft constraints. In spite of theoretical results, [15] has discarded (hyper)tree-decompositions for the benefit of coverings by acyclic hypergraphs in the CSP area. We extend here this work to constraint optimization. We first study these coverings from a theoretical viewpoint. Then we exploit them in a framework aiming not to define a new decomposition, but to make easier a dynamic management of the structure during the search (unlike most of structural methods which usually exploit the structure statically), and so the use of dynamic variable ordering heuristics. Thus, we provide a new complexity result which outperforms significantly the previous one given in the literature. Finally, we assess the practical interest of these notions.

It was shown that constraint satisfaction problems (CSPs) with a low width can be solved efficiently by structural methods. However, these methods often present an important drawback: they generally require a large amount of memory space, what makes their use difficult or impossible. For instance, the BTD method solves efficiently difficult instances thanks to the recording of goods and nogoods. As this recording may require an exponential memory size, the exploitation of a compact data structure is crucial. In this paper, we propose to store (no)goods in binary decision diagrams (BDD). BDDs are data structures which efficiently represent informations in a compact and canonical form. Finally, we assess the practical interest of this tradeoff which allows to save space memory and consequently to solve problems that cannot be solved without BDDs

In this paper, we approach a derivation of the fifth challenge presented on IJCAI 1997 (Selman et al., 1997), that is to detect inconsistency by means of incomplete methods. Whereas this problem is of considerable interest, no significant contribution has emerged since 1997. In order to treat this matter, we review Gaur et al. (1997) that showed how to detect unsatisfiable CSP instances by coloring a graph. We observe that this approach doesn't seem to offer the expected prospects. Anyway, we exploit a similar process that permits to prove graph uncolorability by a CSP consistency check.

We study here a CSP decomposition method introduced in [P. Jegou (1990)] and called cyclic-clustering. While [P. Jegou (1990)] only presents the principles of the method, This work explains how this method can be made operational by exploiting good properties have triangulated induced subgraphs. After, we give formal results, which show that cyclic-clustering proposes a time-space trade-off w.r.t. theoretical complexities. Finally, we present some preliminary experiments, which show that cyclic-clustering may be efficient in practice.

Recently, efficient algorithms have been proposed to achieve arc- and path-consistency in constraint networks. The best path-consistency algorithm proposed is PE-{5|6} which is a natural generalization of AC-6 to path-consistency independently proposed by M. Singh (1995) for PC-5 and A. Chmeiss and P. Jegou (1995) for PC-6. Unfortunately, we have remarked that PC-{5|6}, though it is widely better than PC-4 (Chmeiss and P. Jegou, 1996) was not very efficient in practice, especially for those classes of problems that require an important space to be run. So, we propose a new path-consistency algorithm called PC-8, the space complexity of which is O(n/sup 2/d) but its time complexity is O(n/sup 3/d/sup 4/), i.e. worse than that of PC-{5|6}. However, the simplicity of PC-8 as well as the data structures used for its implementation offer a higher performance than PC-{5|6}. The principle of PC-8 is also used to propose a new algorithm to achieve arc-consistency called AC-8.