Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Bounds arc consistency for weighted CSPs

Abstract : The Weighted Constraint Satisfaction Problem (WCSP) framework allows representing and solving problems involving both hard constraints and cost functions. It has been ap- plied to various problems, including resource allocation, bioinformatics, scheduling, etc. To solve such problems, solvers usually rely on branch-and-bound algorithms equipped with local consistency filtering, mostly soft arc consistency. However, these techniques are not well suited to solve problems with very large domains. Motivated by the resolution of an RNA gene localization problem inside large genomic sequences, and in the spirit of bounds consistency for large domains in crisp CSPs, we introduce soft bounds arc consistency, a new weighted local consistency specifically designed for WCSP with very large domains. Compared to soft arc consistency, BAC provides significantly improved time and space asymptotic complexity. In this paper, we show how the semantics of cost functions can be exploited to further improve the time complexity of BAC. We also compare both in theory and in practice the efficiency of BAC on a WCSP with bounds consistency enforced on a crisp CSP using cost variables. On two different real problems modeled as WCSP, including our RNA gene localization problem, we observe that maintaining bounds arc con- sistency outperforms arc consistency and also improves over bounds consistency enforced on a constraint model with cost variables.
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
Déposant : Migration Prodinra <>
Soumis le : dimanche 31 mai 2020 - 12:53:42
Dernière modification le : lundi 21 septembre 2020 - 19:32:01


Bounds arc consistency for wei...
Fichiers éditeurs autorisés sur une archive ouverte




Matthias Zytnicki, Christine Gaspin, Simon de Givry, Thomas Schiex. Bounds arc consistency for weighted CSPs. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2009, 35, pp.593-621. ⟨10.1613/jair.2797⟩. ⟨hal-02668467⟩



Consultations de la notice


Téléchargements de fichiers