SOLVING LINEAR, MIN AND MAX CONSTRAINT SYSTEMS USING CLP BASED ON RELATIONAL INTERVAL ARITHMETIC

Many real problems can be treated as constraint satisfaction problems (CSPs), a type of problem for which efficient tools have been develope d. Computing the maximum timing separations between the events of a ti ming specification falls into this category. In particular, CLP (BNR) is a constraint logic programming language which seems well suited to the problem, allowing to draw from the advantages of both CSPs and Log ic Programming. Consistency techniques used for solving general CSPs u sually produce approximate answers (partial consistency). However, for some specific timing specifications, that is, systems of strictly lin ear constraints, systems of either max-only or min-only constraints, a nd systems where linear and either max or min constraints intermix, we show that global consistency can be achieved using CLP based on Relat ional Interval Arithmetic.