Given a maritime liner network, the cargo routing problem consists of determining which maritime routes containers will take to be transported from their loading port to their destination port. This constrained optimization problem is an essential task in the context of maritime commodity transportation, both in terms of network design and operational implementation. Several variants of this problem have been considered depending on their usage (e.g. for designing the network or for carrying containers in practice), the constraints taken into account or the criterion to be optimized. In this article, we address several variants of this problem, relying on the flexibility of Constraint Programming. First, we propose two general COP models. Then, we describe a local search method that can be easily adapted to the desired context. Finally, we experimentally compare our two models and the proposed method.

The liner shipping network design problem consists, for a shipowner, in determining, on the one hand, which maritime lines (in the form of rotations serving a set of ports) to open, and, on the other hand, the assignment of ships (container ships) with the adapted sizes for the different lines to carry all the container flows. In this paper, we propose a modeling of this problem using constraint programming. Then, we present a preliminary study of its solving using a state-of-the-art solver, namely the OR-Tools CP-SAT solver.

Benzenoids are a subfamily of hydrocarbons (molecules that are only made of hydrogen and carbon atoms) whose carbon atoms form hexagons. These molecules are widely studied both experimentally and theoretically and can have various physicochemical properties (mechanical resistance, electronic conductivity, ...) from which a lot of concrete applications are derived. These properties can rely on the existence or absence of fragments of the molecule corresponding to a given pattern (some patterns impose the nature of certain bonds, which has an impact on the whole electronic structure). The exhaustive generation of families of benzenoids sharing the absence or presence of given patterns is an important problem in chemistry, particularly in theoretical chemistry, where various methods can be used to better understand the link between their shapes and their electronic properties. In this paper, we show how constraint programming can help chemists to answer different questions around this problem. To do so, we propose different models including one based on a variant of the subgraph isomorphism problem and we generate the desired structures using Choco solver.

Conflict Driven Clause Learning (CDCL) solvers are known to be efficient on structured instances and manage to solve ones with a large number of variables and clauses. An important component in such solvers is the branching heuristic which picks the next variable to branch on. In this paper, we evaluate different strategies which combine two state-of-the-art heuristics, namely the Variable State Independent Decaying Sum (VSIDS) and the Conflict History-Based (CHB) branching heuristic. These strategies take advantage of the restart mechanism, which helps to deal with the heavy-tailed phenomena in SAT, to switch between these heuristics thus ensuring a better and more diverse exploration of the search space. Our experimental evaluation shows that combining VSIDS and CHB using restarts achieves competitive results and even significantly outperforms both heuristics for some chosen strategies.

Reinforcement learning has shown its relevance in designing search heuristics for backtracking algorithms dedicated to solving decision problems under constraints. Recently, an efficient heuristic, called Conflict History Search (CHS), based on the history of search failures was introduced for the Constraint Satisfaction Problem (CSP). The Exponential Recency Weighted Average (ERWA) is used to estimate the hardness of constraints and CHS favors the variables that often appear in recent failures. The step parameter is important in CHS since it controls the estimation of the hardness of constraints and its refinement may lead to notable improvements. The current research aims to achieve this objective. Indeed, a Multi-Armed Bandits (MAB) framework can select an appropriate value of this parameter during the restarts performed by the search algorithm. Each arm represents a CHS with a given value for the step parameter and it is rewarded by its ability to improve the search. A training phase is introduced earlier in the search to help MAB choose a relevant arm. The experimental evaluation shows that this approach leads to significant improvements regarding CHS and other state-of-the-art heuristics.

We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each defines a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.

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.

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.

The main purpose of the paper is to solve structured instances of the satisfiability problem. The structure of a SAT instance is represented by an hypergraph, whose vertices correspond to the variables and the hyper-edges to the clauses. The proposed method is based on a tree decomposition of this hyper-graph which guides the enumeration process of a DPLL-like method. During the search, the method makes explicit some information which is recorded as structural goods and nogoods. By exploiting this information, the method avoids some redundancies in the search, and so it guarantees a bounded theoretical time complexity which is related to the tree-decomposition. Finally, the method is assessed on structured SAT benchmarks.

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.

We propose a new method for solving structured CSPs which generalizes and improves the Cyclic-Clustering approach. First, the cutset and the tree-decomposition of the constraint network, which are used for taking advantage of the CSP structure, are computed independently of the notion of triangulated induced subgraph. Then, unlike Cyclic-Clustering, our method can try to solve the tree-decomposition part of the problem without having assigned all the variables of the cutset. Regarding the solving of the tree-decomposition part, we use the BTD method like in. As BTD records and exploits structural (no)goods, we provide some conditions which make possible the use of structural (no)goods recorded during previous calls of BTD and we implement them in a dedicated version of BTD. By so doing, from a theoretical viewpoint, we can provide a theoretical time complexity bound related to parameters of the cutset and the tree-decomposition and, from a practical viewpoint we expect to detect failures earlier and to avoid more redundancies in the search.

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.

The tree-decomposition notion plays a central role in the frame of the structured CSP solving. On the one hand, it is exploited in many methods like tree-clustering, BTD or cyclic-clustering (CC). It then leads to theoretical time complexity bounds among the best ones. On the other hand, it is often used as a preliminary step for computing a hypertree-decomposition. Unfortunately, finding the best tree-decomposition is a NP-hard problem. So heuristic methods are classically used for computing tree-decompositions. They mostly rely on triangulations of graphs. Sometimes, this approach by triangulation can lead to a rough identification of the structure. Such a drawback can be avoided by considering a cutset such that the remaining problem corresponds to a set of tree-decompositions. In this article, from a cutset and the corresponding set of tree-decompositions, we propose a new method for computing a suitable tree-decomposition w.r.t. CSP solving. Thanks to this approach, we can exploit BTD on the resulting tree-decomposition instead of CC on the cutset and the corresponding set of tree-decompositions. Then, unlike CC, it allows to fully exploit the informations recorded during the search, what leads to avoid some redundancies in the search space. In practice, the first empirical results are very promising since BTD with a tree-decomposition computed with the proposed method outperforms BTD with a tree-decomposition based on triangulation and some other classical algorithms.

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

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.