Approximate constraint satisfaction over a constraint hierarchy: a preliminary study

Given a problem represented as a set of constraints, the goal of constraint satisfaction is to find solutions that satisfy the constraints. A necessary requirement for constraint satisfaction is the discrimination of some potential solutions from others by investigating how well they satisfy constraints. Often, a practical constraint satisfaction problem involves a situation in which one potential solution is evaluated to be better than another if the former satisfies constraints significantly better than the latter does. Approximate constraint satisfaction aims at the selection of solutions or the seriation of potential solutions for such a problem in the presence of the notion of significant difference or “indifference interval”. The underlying idea of approximate constraint satisfaction can be roughly stated that: (1) constraints under consideration are ordered by their importance in the selection of solutions; and (2) when potential solutions´ satisfactions of a constraint are not significantly different, subsequent constraints are used to discriminate the potential solutions. Based on this idea, we propose two methods of approximate constraint satisfaction and discuss their properties