Computer Science @ University of St Andrews

University of St Andrews crest

Constraint Programming

Introduction

Constraints are a powerful and natural means of knowledge representation and inference in many different fields, both in industry and academia. Constraint programming is the solution of combinatorial problems (e.g. scheduling, fault diagnosis) in two stages. First, by characterising or modelling them by a set of constraints on decision variables that their solutions must satisfy. Second, by searching for solutions with a constraint solver: assignments to the decision variables that satisfy all constraints. Our research encompasses both modelling and solving phases.

As a simple example, consider the classic puzzle of trying to place n queens on an n x n chess board so that no two queens are attacking each other. There are many possible models of this problem. For instance, one might have a decision variable for each square of the board, each with two possible values corresponding to whether a queen is or is not occupying that square. However, we can simplify the model considerably by recognising that each row contains exactly one queen. Therefore, another option is to have one variable per row, specifying the column on that row that the associated queen occupies. Clearly, we could also take a column-centric, or even diagonal-centric view of modelling the problem. Modelling choices such as these have a substantial effect on the efficiency with which a constraint problem can be solved. Selecting a good model takes a great deal of experience and expertise, which can take many years to acquire. By encoding human modelling expertise in an automated modelling assistant, we are reducing this modelling bottleneck.

The n-queens problem also exhibits a large amount of symmetry. Given any solution, we can obtain another by rotating or reflecting the board. These solutions are symmetrically equivalent. We can exploit symmetry by searching only for symmetrically unique solutions, thus reducing the overall amount of search needed substantially. To do this, we use the mathematical study of such symmetric situations, called group theory. By integrating modern tools for computational group theory with constraint programming tools, we can break all the symmetry in a problem. This is leading to exciting interdisciplinary research between Artificial Intelligence and Mathematics.

People

Projects


This page is maintained by Ian Gent.