Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning

AbstractWe study the problems of deciding consistency and performing variable elimination for disjunctions of linear inequalities and disequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. We show that deciding consistency of a set of constraints in this class can be done in polynomial time. We also present a variable elimination algorithm which is similar to Fourier's algorithm for linear inequalities. Finally, we use these results to provide new temporal reasoning algorithms for the Ord-Horn subclass of Allen's interval formalism. We also show that there is no low level of local consistency that can guarantee global consistency for the Ord-Horn subclass. This property distinguishes the Ord-Horn subclass from the pointizable subclass (for which strong 5-consistency is sufficient to guarantee global consistency), and the continuous endpoint subclass (for which strong 3-consistency is sufficient to guarantee global consistency)