Meta-constraints on violations for over constrained problems

Abstract

Constraint programming techniques are widely used to solve real-world problems. It often happens that such problems are over-constrained and do not have any solution. In such a case, the goal is to find a good compromise. A simple theoretical framework is the Max-CSP, where the goal is to minimize the number of constraint violations. However, in real-life problems, complex rules are generally imposed with respect to violations. Solutions which do not satisfy these rules have no practical interest. Therefore, many frameworks derived from the Max-CSP have been introduced. In this paper, we classify the most usual types of rules, and we show that some of them are not expressible in existing frameworks. We introduce a new paradigm in which all these rules can be encoded, through meta-constraints. Moreover, we show that most of existing frameworks can be included in our model.