A General Conflict-Set Based Framework for Partial Constraint Satisfaction

Abstract : Partial constraint satisfaction [5] was widely studied in the 90's, and notably Max-CSP solving algorithms [21, 20, 1, 10]. These algorithms compute a lower bound of violated constraints without using propagation. Therefore, recent methods focus on the exploitation of propagation mechanisms to improve the solving process. Soft arc-consistency algorithms [11, 18, 19] propagate inconsistency counters through domains. Another technique consists of using constraint propagation to identify conflict-sets which are pairwise disjoint [16]; the number of conflict-sets extracted leads to a lower bound. In this paper, we place this technique in a more general context. We show this technique reduces to a polynomial case of the NP-Complete Hitting Set problem. Conflict-sets are chosen disjoint to compute the lower bound polynomially. We present a new polynomial case where the conflict-sets share some constraints, and a third case which is not polynomial but such that the cardinality of the Hitting Set can be reasonably under estimated. For each one we provide the algorithm and a schema to generate incrementally the conflict-set collection. We show its extension to weighted CSPs.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269780
Contributor : Christine Carvalho de Matos <>
Submitted on : Tuesday, February 21, 2017 - 4:04:41 PM
Last modification on : Monday, November 5, 2018 - 3:48:02 PM
Long-term archiving on : Monday, May 22, 2017 - 3:53:34 PM

File

A General Conflict-Set.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00269780, version 1

Citation

Thierry Petit, Christian Bessière, Jean-Charles Régin. A General Conflict-Set Based Framework for Partial Constraint Satisfaction. Soft Constraints, 2003, Cork, Ireland. ⟨lirmm-00269780⟩

Share

Metrics

Record views

282

Files downloads

268