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.
Type de document :
Communication dans un congrès
S. Bistarelli; J. Larrosa; T. Schiex. Soft Constraints, 2003, Cork, Ireland. 5th International Workshop on Soft Constraints held in conjunction with 9th International Conference on Principles and Practice of Constraint Programming, CP2003, 2003
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269780
Contributeur : Christine Carvalho de Matos <>
Soumis le : mardi 21 février 2017 - 16:04:41
Dernière modification le : vendredi 24 février 2017 - 01:06:19

Fichier

A General Conflict-Set.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00269780, version 1

Collections

Citation

Thierry Petit, Christian Bessière, Jean-Charles Régin. A General Conflict-Set Based Framework for Partial Constraint Satisfaction. S. Bistarelli; J. Larrosa; T. Schiex. Soft Constraints, 2003, Cork, Ireland. 5th International Workshop on Soft Constraints held in conjunction with 9th International Conference on Principles and Practice of Constraint Programming, CP2003, 2003. <lirmm-00269780>

Partager

Métriques

Consultations de
la notice

47

Téléchargements du document

21