toulbar2
Soft arc consistency and problem reformulation

Soft arc consistency is an incremental lower bound technique for optimization problems. Its goal is to move costs from high-order (typically arity two or three) cost functions towards the problem lower bound and unary cost functions. This is achieved by applying iteratively local equivalence-preserving problem transformations (EPTs) until some terminating conditions are met.

Note
eg an EPT can move costs between a binary cost function and a unary cost function such that the sum of the two functions remains the same for any complete assignment.
See also
Arc consistency for Soft Constraints. T. Schiex. Proc. of CP'2000. Singapour, 2000.
Note
Soft Arc Consistency in toulbar2 is limited to binary and ternary and some global cost functions (eg alldifferent, gcc, regular, same). Other n-ary cost functions are delayed for propagation until their number of unassigned variables is three or less.
See also
Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction. Jimmy Ho-Man Lee, Ka Lun Leung. Proc. of IJCAI 2009, pages 559-565. Pasadena, USA, 2009.