Solving linear, min and max constraint systems using CLP based on relational interval arithmetic

AbstractMany real problems can be treated as constraint satisfaction problems (CSPs), a type of problem for which efficient tools have been developed. Computing the maximum timing separations between the events of a timing 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 Logic Programming. Consistency techniques used for solving general CSPs usually produce approximate answers (partial consistency). However, for some specific timing specifications, that is, systems of strictly linear constraints, systems of either max-only or min-only constraints, and systems where linear and either max or min constraints intermix, we show that global consistency can be achieved using CLP based on Relational Interval Arithmetic