Flexibility as relaxation -- the fuzzy set view

Abstract. In Fuzzy Constraints Satisfaction Problem (FCSP), fuzzy constraints are aggregated by min operation into a fuzzy set membership function to be maximized. This representation framework, originally expressed in terms of membership functions, can be equivalently translated into a set of prioritized crisp constraints. We take advantage of this representation for modeling aggregations different from min, expressing either reinforcement or compensation. The approach offers a logical understanding of fuzzy constraints, which enable us to explicit the relaxation space, attached to a FCSP. This relaxation space concept can be defined independently of fuzzy constraints based on the concept of constraint relaxation. In a relaxation space the usual task is to find a less relaxed consistent problem. A binary search approach is then proposed to find such problems while minimizing the number of relaxation space problems that are checked. 1