On Supporting Dynamic Constraint Satisfaction with Order of Magnitude Preferences

Keppens, J. and Shen, Q.

Proceedings of the 16th International Workshop on Qualitative Reasoning. 75-82.

July 2002

Abstract

Many application problems can be formulated as dynamic preference constraint satisfaction problems. Such a problem employs activity constraints that govern what attributes and constraints are part of the current problem description, and has a preference associated with each of the domain values. The preferences can be combined using any commutative, associative and monotonic operator to compute the preference of the overall solution. The important problem of expressing user preference under incomplete knowledge and combining them has not been addressed however. This paper introduces an order of magnitude preference (OMP) calculus to handle reasoning with preferences. The benefits of this calculus are twofold. Firstly, it allows for a partial ordering of preferences, rather than the usually imposed total ordering, thereby simplifying the knowledge required for problem formulation. Secondly, computational efficiency can be improved in solving complex problems as the OMP calculus ignores those preferences that are an order of magnitude lower than the ones that make a real difference to the overall quality of an emerging solution.

Download PDF document