Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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.
Type de document :
Article dans une revue
Liste complète des métadonnées
Déposant : Migration Prodinra <>
Soumis le : samedi 30 mai 2020 - 23:44:09
Dernière modification le : lundi 21 septembre 2020 - 19:32:01




Martin C. 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⟩



Consultations de la notice