Constraints

A special invited session on Constraints, consisting solely of invited talks, has been organized by Eugene C. Freuder (Constraint Computation Center and Department of Computer Science, University of New Hampshire, Durham, NH 03824). 

Introduction

Constraint computation is emerging as a major new computing paradigm out of developments in artificial intelligence, programming languages, operations research, discrete mathematics, and other fields.

Many problems are naturally viewed as Constraint Satisfaction Problems, consisting of variables with domains of potential values, and constraints specifying which combinations of values are allowed. For example, in a graph coloring problem, the variables are the vertices, the values are the colors, and the constraints specify that neighboring vertices have different colors. AI applications are found in many areas, including planning, design, diagnosis, and robotics. There is a natural extension to constraint optimization.

Mathematics has supported the theoretical underpinnings of constraint computation and informed the development of constraint satisfaction algorithms. For example:

Constraint programming in turn has tackled hard mathematical problems. For example:

Talks in the Session