Bounds arc consistency for weighted CSPs - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Article Dans Une Revue Journal of Artificial Intelligence Research Année : 2009

Bounds arc consistency for weighted CSPs

Résumé

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.
Fichier principal
Vignette du fichier
Bounds arc consistency for weighted CSPs_MZ CG SDG TS_1.pdf (324.84 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02668467 , version 1 (31-05-2020)

Identifiants

Citer

Matthias Zytnicki, Christine Gaspin, Simon de Givry, Thomas Schiex. Bounds arc consistency for weighted CSPs. Journal of Artificial Intelligence Research, 2009, 35, pp.593-621. ⟨10.1613/jair.2797⟩. ⟨hal-02668467⟩
14 Consultations
17 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More