Speaker: Karen Petrie (Dundee)

Title: Why is Computational Group Theory Important to Constraint Programming?


Problems often consist of choices. Making an optimal choice which is compatible with all other choices made is difficult. Constraint programming (CP) is the branch of Artificial Intelligence, where computers help us to make these choices. Constraint programming is a multidisciplinary technology combining computer science, operational research and mathematics. CP can solve problems in telecommunication, e-commerce, electronics, bioinformatics, transportation, network management, supply chain management, and many other fields. A constraint program consists of a set of variables, a set of possible values, for each variable and a set of constraints. For example, the problem might be to fit components (values) to circuit boards (variables), subject to the constraint that no two components can be overlapping. A solution to a CSP is an allocation of values to variables such that none of the constraints are violated. In recent years computational group theory techniques have become important to CP solvers. I will outline why this is and then try to indicate where the open problems lie.