Arc consistency for soft constraints

The notion of arc consistency plays a central role in constraint satisfaction [R. Dechter, Constraint Processing, Morgan Kaufmann, San Mateo, CA, 2003]. It is known since the introduction of valued and semi-ring constraint networks in 1995 that the notion of local consistency can be extended to constraint optimisation problems defined by soft constraint frameworks based on an idempotent cost combination operator. This excludes non-idempotent operators such as + which define problems which are very important in practical applications such as MAX-CSP, where the aim is to minimise the number of violated constraints. In this paper, we show that using a weak additional axiom satisfied by most existing soft constraints proposals, it is possible to define a notion of soft arc consistency that extends the classical notion of arc consistency and this even in the case of non-idempotent cost combination operators. A polynomial time algorithm for enforcing this soft arc consistency exists and its space and time complexities are identical to that of enforcing arc consistency in CSPs when the cost combination operator is strictly monotonic (for example MAX-CSP). A directional version of arc consistency, first introduced by M.C. Cooper [Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets and Systems 134 (3) (2003) 311-342] is potentially even stronger than the non-directional version, since it allows non-local propagation of penalties. We demonstrate the utility of directional arc consistency by showing that it not only solves soft constraint problems on trees, but that it also implies a form of local optimality, which we call arc irreducibility. (C) 2003 Elsevier B.V. All rights reserved.