CONSTRAINTS: A PROGRAMMING PARADIGM AND A MODELLING METHODOLOGY

Abstract

Constraints are often used as a formal approach to problems, because the very essence of the problem can be grasped by them. A lot of problems can be viewed as a set of variables and a set of relations on them. From this point of view the problem can be mapped naturally to a constraint network (the nodes of the network represent the variables; and the constraints in the network represent the relations between the variables of the problem); and this gives great significance to the research on constraints. An additional advantage is that they achieve global consistency through local computations. Constraints and the Constraint Satisfaction Problem (CSP) can be classified by various criteria. The most significant classification is based on the type of the values assigned to the nodes. Another possible classification of CSP is based on the kind of the required solution. Significant effort was invested in developing general constraint programming languages (CPL) to provide an environment where the only thing a user has to do is to declare what she/he wants, not bothering how it is done. Though these languages aimed at generality, due to the limited ability of data abstraction and higher order constraints they could not fully achieve their goal. If the main stress is on the efficiency, dedicated solutions claim their place with their unique data structures and specialised constraint satisfaction algorithms. The main goal of this paper is to give an overview of constraints as a flexible knowledge representation tool; to draw attention to the problems of representation and to methods of finding the solutions of the different types of constraint networks.