Clique inference process for solving Max-CSP
Few works on problems CSP, Max-CSP and weighted CSP was carried out in the field of Combinatorial Optimization, whereas this field contains many algorithmic tools which can be used for the resolution of these problems. In this paper, we introduce the binary clique concept: clique which expresses incompatibilities between values of two CSP variables. We propose a linear formulation for any binary clique and we present several ways to exploit it in order to compute lower bounds or to solve Max-CSP. We also show that the binary clique concept can be exploited in the weighted CSP framework. The obtained theoretical and experimental results are very interesting and they open new prospects to exploit the Combinatorial Optimization algorithmic tools for the resolution of CSP, Max-CSP and weighted CSP.
Year of publication: |
2009
|
---|---|
Authors: | Khemmoudj, Idir ; Ou, Mohand ; Bennaceur, Hachemi |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 199.2009, 3, p. 665-673
|
Publisher: |
Elsevier |
Keywords: | Binary clique Max-CSP lower bounds Linear programming |
Saved in:
Saved in favorites
Similar items by person
-
Clique inference process for solving Max-CSP
Idir Khemmoudj, Mohand Ou, (2009)
-
Bennaceur, Hachemi, (1998)
-
Clique inference process for solving Max-CSP
Khemmoudj, Mohand Ou Idir, (2009)
- More ...