Summary: Traditionally, local consistency is defined as a relaxation of consistency which can be checked in polynomial time. It is accompanied by a corresponding “filtering” or ”enforcing” algorithm that computes in polynomial time, and from any given CSP, an equivalent unique CSP which satisfies the local consistency property.
The question whether the notion of local consistency can be extended to soft constraint frameworks has been addressed by several papers, in several settings. The main positive conclusion of these works is that the notion of local consistency can be extended to soft constraints frameworks which rely on an idempotent violation combination operator. However, the question whether this can be done for non idempotent operators as eg, in the MAX-CSP problem, is not clear and has lead to several different notions of arc consistency. Each of these proposals lacks several of the original properties of local consistency.
In this paper, we show that using a small additional axiom, satisfied by most existing soft constraints proposals (including MAX-CSP), it is possible to define a notion of arc consistency that keeps all the good properties of classical arc consistency but the unicity of the arc consistent closure. We show that this notion directly provides improved lower bounds. Stronger alternative definitions, that allow partial inconsistencies to propagate are also considered.
For the entire collection see [Zbl 0947.00041].