Author name cluster

Assef Chmeiss

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.

3 papers

2 author rows

ECAI Conference 2008 Conference Paper

Redundancy in CSPs

Assef Chmeiss
Vincent Krawczyk
Lakhdar Saïs

In this paper, we propose a new technique to compute irredundant sub-sets of constraint networks. Since, checking redundancy is Co-NP Complete problem, we use different polynomial local consistency entailments for reducing the computational complexity. The obtained constraint network is irredundant modulo a given local consistency. Redundant constraints are eliminated from the original instance producing an equivalent one with respect to satisfiability. Eliminating redundancy might help the CSP solver to direct the search to the most constrained (irredundant) part of the network.

Details

IJCAI Conference 2003 Conference Paper

On a generalization of triangulated graphs for domains decomposition of CSPs

Assef Chmeiss
Philippe Je'gou
Lamia Keddar

In [Jegou, 1993], a decomposition method has been introduced for improving search efficiency in the area of Constraint Satisfaction Problems. This method is based on properties of micro-structure of CSPs related to properties of triangulated graphs. This decomposition allows to transform an instance of CSP in a collection of sub-problems easier to solve, and then gives a natural and efficient way for a parallel implementation [Habbas et al, 2000]. In this paper, we present a generalization of this approach, which is based on a generalization of triangulated graphs. This generalization allows to define the level of decomposition which can be fixed by a graph parameter. The larger this parameter is, the more level of decomposition that is the number of sub-problems is. As a consequence, we can then define the level of decomposition, with respect to the nature of the parallel configuration used (the number of processors). First experiments reported here show that this extension increases significantly the advantage of the basic decomposition, already shown in [Habbas et al, 2000].

PDF

AAAI Conference 1996 Conference Paper

Path-Consistency: When Space Misses Time

Assef Chmeiss

Within the framework of constraint programming, particulary concerning the Constraint Satisfaction Problems (CSPs), the techniques of preprocessing based on filtering algorithms were shown to be very important for the search phase. In particular, two filtering methods have been studied, these methods exploit two properties of local consistency: arcand path-consistency. Concerning the arc-consistency methods, there is a linear time algorithm (in the size of the problem) which is efficient in practice (Bessiere, Freuder, & R&gin 1995). But the limitations of the arc-consistency algorithms requires often filtering methods with higher order like path-consistency filterings. The best path-consistency algorithm proposed is PC-6, a natural generalization of AC-6 (Bessiere 1994) to path-consistency (Chmeiss & Je 5 ou 1995)(Chmeiss 1996). Its time complexity is O(n d3) and its space complexity is O(n3d2), where n is the number of variables and d is the size of domains. We have remarked that PC-G, though it is widely better than PC-4 (Han & Lee 19SS), was not very efficient in practice, specialy for those classes of problems that require an important space to be run. Therefore, we propose here a new path-consistency algorithm called PC-7, its space complexity is O(n2d2) but its time complexity is O(n3d4) i. e. worse than that of PC-G. However, the simplicity of PC-7 as well as the data structures used for its implementation offer really a higher performance than PC-6. Furthermore, it turns out that when the size of domains is a constant of the problems, the time compPexity of PC-7 becomes, like PC-6, optimal i. e. O(n3).

PDF Details