Track:
All Papers
Downloads:
Abstract:
Preferences in constraint problems are common but significant in many real world applications. In this paper, we extend our conditional and composite CSP (CCCSP) framework, managing CSPs in a dynamic environment, in order to handle preferences. Unlike the existing CSP models managing one form of preferences, ours supports four types, namely: variable value and constraint preferences, composite preferences and conditional preferences. This offers more expressive power in representing a wide variety of constraint problems. The preferences are considered here as a set of soft constraints using a c-semiring structure with combination and projection operators. Solving constraint problems with preferences consists of finding a solution satisfying all the constraints while optimizing the preference values. This is handled by a variant of the branch and bound algorithm, we propose in this paper, and where constraint propagation is used to improve the time efficiency. Experimental tests, we conducted on randomly generated CCCSPs with preferences, favor the MAC principle as the constraint propagation strategy to be used within the branch and bound procedure.