Arrow Research search

Author name cluster

Philippe Jégou

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
2 author rows

Possible papers

8

AAAI Conference 2015 Conference Paper

The Extendable-Triple Property: A New CSP Tractable Class beyond BTP

  • Philippe Jégou
  • Cyril Terrioux

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 (Cooper, Jeavons, and Salamon 2010)) 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.

PDF Details

ECAI Conference 2014 Conference Paper

Combining Restarts, Nogoods and Decompositions for Solving CSPs

  • Philippe Jégou
  • Cyril Terrioux

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.

Details

AAAI Conference 1993 Conference Paper

Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems

  • Philippe Jégou

In this paper, we present a method for improving search efficiency in the area of Constraint- Satisfaction-Problems in finite domains. This method is based on the analysis of the “micro-structure” of a CSP. We call micro-structure of a CSP, the graph defined by the compatible relations between variablevalue pairs: vertices are these pairs, and edges are defined by pairs of compatible vertices. Given the micro-structure of a CSP, we can realize a preprocessing to simplify the problem with a decomposition of the domains of variables. So, we propose a new approach to problem decomposition in the field of CSPs, well adjusted in cases such as classical decomposition methods are without interest (i. e. when the constraint graph is complete). The method is described in the paper and a complexity analysis is presented, given theoretical justifications of the approach. Furthermore, two polynomial classes of CSPs are induced by this approach, the recognition of them being linear in the size of the instance of CSP considered.

PDF Details

AAAI Conference 1993 Conference Paper

On the Consistency of General Constraint-Satisfaction Problems

  • Philippe Jégou

The problem of checking for consistency of Constraint-Satisfaction Problems (CSPs) is a fundamental problem in the field of constraint-based reasonning. Moreover, it is a hard problem since satisfiability of CSPs belongs to the class of NPcomplete problems. So, in (Freuder 1982), Freuder gave theoretical results concerning consistency of binary CSPs (two variables per constraints). In this paper, we proposed an extension to these results to general CSP (n-ary constraints). On one hand, we define a partial consistency well adjusted to general CSPs called hyper-k-consistency. On the other hand, we proposed a measure of the connectivity of hypergraphs called width of hypergraphs. Using width of hypergraphs and hyper-kconsistency, we derive a theorem defining a sufficient condition for consistency of general CSPs.

PDF Details