A General Conflict-Set Based Framework for Partial Constraint Satisfaction - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2003

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.
Fichier principal
Vignette du fichier
A General Conflict-Set.pdf (132.27 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00269780 , version 1 (21-02-2017)

Identifiers

  • HAL Id : lirmm-00269780 , version 1

Cite

Thierry Petit, Christian Bessiere, Jean-Charles Régin. A General Conflict-Set Based Framework for Partial Constraint Satisfaction. Soft Constraints, 2003, Cork, Ireland. ⟨lirmm-00269780⟩
277 View
172 Download

Share

Gmail Mastodon Facebook X LinkedIn More