Skip to Main content Skip to Navigation
Journal articles

Soft arc consistency revisited

Abstract : The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations Research, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search. In this paper, we extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal arc consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC). To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft arc consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions. These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.
Document type :
Journal articles
Complete list of metadata

https://hal.inrae.fr/hal-02662237
Contributor : Migration Prodinra Connect in order to contact the contributor
Submitted on : Saturday, May 30, 2020 - 11:44:09 PM
Last modification on : Monday, September 6, 2021 - 3:36:04 PM

Links full text

Identifiers

Collections

Citation

Martin Cooper, Simon de Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki, et al.. Soft arc consistency revisited. Artificial Intelligence, Elsevier, 2010, pp.449-478. ⟨10.1016/j.artint.2010.02.001⟩. ⟨hal-02662237⟩

Share

Metrics

Record views

37