@Article{Cooper-AI-2010,
  IS = { zkontrolovano 19 Oct 2010 },
  UPDATE  = { 2010-10-19 },
  author = {Cooper, M. C. and de Givry, S. and Sanchez, M. and 
            Schiex, T. and Zytnicki, M. and Werner, T.},
  title = {Soft arc consistency revisited},
  journal = {Artificial Intelligence},
  volume = {174},
  number = {7-8},
  year = {2010},
  issn = {0004-3702},
  pages = {449--478},
  publisher = {Elsevier Science Publishers Ltd.},
  address = {Essex, UK},
  authorship =  {20-20-15-15-15-15},
  project = {ICT-215078 DIPLECS},
  annote = {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.},
month       = { May },
keywords    = { Valued constraint satisfaction problem, Weighted
   constraint satisfaction problem, Soft constraints, Constraint
   optimization, Local consistency, Soft arc consistency, Graphical
   model, Submodularity },
}