Cyclic consistency: A local reduction operation for binary valued constraints

Valued constraint satisfaction provides a general framework for optimisation problems over finite domains. It is a generalisation of crisp constraint satisfaction allowing the user to express preferences between solutions.Consistency is undoubtedly the most important tool for solving crisp constraints. It is not only a family of simplification operations on problem instances; it also lies at the heart of intelligent search techniques [G. Kondrak, P. van Beek, Artificial Intelligence 89 (1997) 365–387] and provides the key to solving certain classes of tractable constraints [P.G. Jeavons, D.A. Cohen, M.C. Cooper, Artificial Intelligence 101 (1998) 251–265].Arc consistency was generalised to valued constraints by sacrificing the uniqueness of the arc consistency closure [M.C. Cooper, T. Schiex, Artificial Intelligence, in press]. The notion of 3-cyclic consistency, introduced in this paper, again sacrifices the uniqueclosure property in order to obtain a generalisation of path consistency to valued constraints which is checkable in polynomial time. In MAX-CSP, 3-cyclic consistency can be established in polynomial time and even guarantees a local form of optimality. The space complexity of 3-cyclic consistency is optimal since it creates no new constraints.