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.