Paper Info
Title
Fast algebraic methods for interval constraint problems
Abstract
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 is the number of variables, and c is the ratio of non‐trivial constraints to possible constraints.
Year
DOI
Venue
1997
10.1023/A:1018968024833
Ann. Math. Artif. Intell.
Keywords
Field
DocType
Constraint Satisfaction Problem,Algebraic Method,Relation Algebra,Pointisable Relation,Constraint Problem
Discrete mathematics,Constraint algebra,Branching factor,Local consistency,Algebraic number,Constraint satisfaction problem,Constraint logic programming,Mathematics,Relation algebra,Binary constraint
Journal
Volume
Issue
ISSN
19
3-4
1573-7470
Citations 
PageRank 
References 
22
1.97
23
Authors
2
Name
Order
Citations
PageRank
Peter B. Ladkin162690.51
Alexander Reinefeld2889126.08