Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Sunday, May 31, 2020 - 12:53:42 PM
Last modification on : Monday, April 11, 2022 - 10:39:23 AM


Bounds arc consistency for wei...
Publisher files allowed on an open archive




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⟩



Record views


Files downloads