On Global Warming: Flow-Based Soft Global Constraints

In case a CSP is over-constrained, it is natural to allow some constraints, called soft constraints, to be violated. We propose a generic method to soften global constraints that can be represented by a flow in a graph. Such constraints are softened by adding violation arcs to the graph and then computing a minimum-weight flow in the extended graph to measure the violation. We present efficient propagation algorithms, based on different violation measures, achieving domain consistency for the alldifferent constraint, the global cardinality constraint, the regular constraint and the same constraint.