Integrating an algorithm for solving linear constraints in finite domains in the language CHIP

Nicolas Beldiceanu and Evelyne Contejean and Helmut Simonis

Abstract: CHIP is a constraint logic programming language originally designed and developed at ECRC [2], and further developed and marketed by COSYTEC. CHIP is able to solve among other constraints (on rationals and booleans), linear constraints over finite integer domains. In this case, its basic mechanism is the combination of constraint propagation and enumeration of the values in the domain associated with the given constraints. In this paper we present an original enumeration method based on an algorithm for solving systems of linear Diophantine equations due to E. Contejean and H. Devie [1]. The difficulty is to show that this enumeration method is compatible with constraint propagation, and that every solution is computed exactly once.


E. Contejean and H. Devie. Résolution de systèmes linéaires d’équations diophantiennes. Comptes-Rendus de l’Académie des Sciences de Paris, 313:115–120, 1991. Série I.
M. Dincbas, P. V. Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F.Berthier. The Constraint Logic Programming Language CHIP. In Proc. Int. Conf. on Fifth Generation Computer Systems FGCS-88, pages 693–702, Tokyo, 1988.

Full Paper

This document was translated from LATEX by HEVEA.