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 applied 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 consistency outperforms arc consistency and also improves over bounds
consistency enforced on a constraint model with cost variables.
