Tech Report CS-91-23

Efficient Handling of Disequations in CLP Over Linear Rational Arithmetic

Jean-Louis Imbert and Pascal Van Hentenryck

March 1991

Abstract:

This paper considers the (efficient) handling of disequations for a CLP language over linear rational (resp. real) arithmetic (based on the simplex algorithm). It discusses both solved forms for the constraints and algorithms to transform systems of constraints into solved form.

The starting point of the paper is a syntactic solved form for equations and disequations which precludes the presence of fixed variables (or hidden constants). Several subclasses of constraints that occur frequently and can be handled more efficiently are then identified. This leads to the definition of an improved solved form that reduces the computational burden imposed on the constraint-solving algorithm.

An incremental algorithm to obtain the improved solved form is then proposed. Its main feature is to exploit the possibility of lazy dereferencing offered by the improved solved form while still detecting all fixed variables. Two important refinments of the algorithm are then described, formally justified, and included in the algorithm. The first improvement avoids checking disequations altogether for an important class of constraints, while the second improvement allows a more active use of disequations, achieving an early detection of failures and precluding unnecessary calls to the simplex algorithm.

(complete text in pdf)