The CP(Graph) computation domain in constraint programming

Constraint programming (CP) aims at modeling and solving constraint satisfaction problems. These problems consist of a set of variables, each with a set of potential values and a set of constraints imposed on the variables. In CP, these problems are solved by decomposing the problems in subproblems until these subproblems are straightforward to solve. With CP(Graph), we introduce graph variables whose domain of values (a set of graphs) is approximated by a graph interval and graph constraints over these variables. While all CP solvers support finite domains (i.e. a range of integers), some now include set variables which ease the modeling of problems involving sets. Together with so-called global constraints, these global variable types allow an higher-level modeling for the CP user and a better exploitation of the structure of the problem by the constraint solver. The filtering task for a constraint consists in identifying sets of values which cannot belong to a solution of the constraint. By removing these values which belong to no solution, the search space is reduced. We propose filtering algorithms for several constraints modeling graph properties and relations. These algorithms use techniques and data structures from discrete algorithmics but focus on a different problem: instead of finding one solution of a graph problem, the task consists in finding the union and the intersection of all the solutions of this graph problem. A proof of concept of this framework has been implemented on top of the Gecode constraint programming library and applied to constrained metabolic pathway extraction and constrained graph matching. It is available under an open-source license.(FSA 3) -- UCL, 200