Matrix-represented constraints satisfaction methods: practical aspects of their implementation

Abstract

The paper proposes an original approach to solving the problem of ineffective processing of qualitative constraints of a subject domain in the framework of constraint programming technology. The approach is based on the use of specialized matrix-like structures, providing a "compressed" representation of constraints over finite domains, as well as using author’s infer- ence algorithms on these structures. Compared to the prototypes using the typical representation of multi-place relations in a form of tables, the techniques make it possible to more efficiently reduce the search space. The paper presents practical aspects of implementation of user-developed types of constraints and corresponding algorithms-propagators with the help of constraint programming libraries. The algorithms performance has been assessed to clearly demonstrate the advantages of representation and processing of qualitative constraints of a subject domain by means of the above matrix structures.