Clique inference process for solving Max-CSP Idir Khemmoudj, Mohand Ou; Bennaceur, Hachemi

User activity

Share to:
View the summary of this work
Idir Khemmoudj, Mohand Ou ; Bennaceur, Hachemi
Appears In
European Journal of Operational Research
Business, general; Business, international; Business
Academic; Trade
To link to full-text access for this article, visit this link: Byline: Mohand Ou Idir Khemmoudj, Hachemi Bennaceur Keywords: Binary clique; Max-CSP lower bounds; Linear programming Abstract: 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. Author Affiliation: LIPN-CNRS UMR 7030, 99 Av. J-B. Clement, 93430 Villetaneuse, France Article History: Received 8 September 2006; Accepted 7 June 2007
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users