Abstract:
Constraint Hierarchies in Constraint Logic Programming Languages
Houria is an incremental solver that proposes a new implementation of constraint hierarchi
es. Houria uses local propagation to maintain sets of required and preferential constraints. I
t represents constraints between variables by sets of short procedures (methods) and increment
ally re-satisfies the set of constraints when individual constraints are added and removed. Th
e criteria of comparison used in this solver are global. They allow the comparison of valuatio
ns, which are not comparable by local criteria used in existing solvers. The solution found by
Houria satisfies more constraints than the one produced by other solvers and that for the sam
e over-constrained problems while respecting the semantics of the hierarchy. We also propose a
n efficient algorithm that integrates the Houria solver in the CLP paradigm.