Skip to Main content Skip to Navigation
Conference papers

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 metadata
Contributor : Christine Carvalho de Matos <>
Submitted on : Tuesday, February 21, 2017 - 4:04:41 PM
Last modification on : Monday, January 11, 2021 - 5:24:05 PM
Long-term archiving on: : Monday, May 22, 2017 - 3:53:34 PM


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


  • HAL Id : lirmm-00269780, version 1


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⟩



Record views


Files downloads