Solving hierarchies of finite-domain constraints
ARMIN WOLF · Journal of Experimental & Theoretical Artificial Intelligence · 1998
. In the past we presented an algorithm to solve ordered constraint hierarchies based on a non-trivial error function using standard constraint satisfaction techniques. We extended this previous work and herewith present a new method to transform hierarchies of inequalities over the integers based on global comparators into equivalent ordered constraint hierarchies. The correctness of this method is proven. Using the results of our previous work, we present another method transforming the resulting ordered constraint hierarchies into ordinary constraint systems. These systems of algebraic equalities and inequalities over the integer domain are soluble with available finite-domain constraint solvers. Finally, we propose some modifications and simplifications of the considered constraint hierarchies, improving the search for solutions and being useful in practical applications like job-shop scheduling. The modifications proposed are the combination of consecutive hierarchy levels in one level where the constraints are considered with different priorities weights and the simplifications proposed are incomplete search strategies resulting in run-time improvements and also in sub-optimal solutions.