Clique inference process for solving Max-CSP

Mohand Ou Idir Khemmoudj and Hachemi Bennaceur

European Journal of Operational Research, 2009, vol. 199, issue 3, 665-673

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.

Keywords: Binary; clique; Max-CSP; lower; bounds; Linear; programming (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00364-0
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:199:y:2009:i:3:p:665-673

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().