Fast algebraic methods for interval constraint problems

We describe an effective generic method for solving constraint problems, based on Tarski’s relation algebra, using path-consistency as a pruning technique. We investigate the performance of this method on interval constraint problems. Time performance is affected strongly by the path-consistency calculations, which involve the calculation of compositions of relations. We investigate various methods of tuning composition calculations, and also path-consistency computations. Space performance is affected by the branching factor during search. Reducing this branching factor depends on the existence of ‘nice’ subclasses of the constraint domain. Finally, we survey the statistics of consistency properties of interval constraint problems. Problems of up to 500 variables may be solved in expected cubic time. Evidence is presented that the ‘phase transition’ occurs in the range 6 ≤ n.c ≤15, where n is the number of variables, and c is the ratio of non-trivial constraints to possible constraints. This revised version was published online in June 2006 with corrections to the Cover Date.