zbMATH — the first resource for mathematics

Fast algebraic methods for interval constraint problems. (English) Zbl 0880.68012
Summary: 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\leq n\cdot c\leq 15\), where \(n\) is the number of variables, and \(c\) is the ratio of non-trivial constraints to possible constraints.

68N17 Logic programming
Full Text: DOI