Bounds arc consistency for weighted CSPs - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Journal Articles Journal of Artificial Intelligence Research Year : 2009

Bounds arc consistency for weighted CSPs


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
Origin : Publisher files allowed on an open archive

Dates and versions

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



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 View
17 Download



Gmail Facebook X LinkedIn More