Abstract
Few works on problems CSP, Max-CSP and weighted CSP was carried out in the field of Combinatorial Optimization, whereas this held 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. (C) 2008 Elsevier B.V. All rights reserved.