Constraint Satisfaction: The Modeling Challenge
Eugene C. Freuder
Constraint Computation Center
Department of Computer Science
University of New Hampshire
Abstract
Constraint programming provides powerful tools for solving declarative
formulae ons of complex combinatorial problems.
Constraint programming is an emerging field with contributions from:
- Artificial Intelligence
- Biocomputing
- Algorithms
- Computational Logic
- Databases
- Discrete Mathematics
- Operations Research
- Parallel/Distributed/Agent Computation
- Programming Languages
- Symbolic Computation.
Application domains include:
- Bioinformatics
- Computer and Communication Networks
- Design and Configuration
- Graphics, Visualization, Interfaces
- Hardware Verification and Software Engineering
- Human-Computer Interaction and Decision Support
- Qualitative and Diagnostic Reasoning
- Real-Time Systems
- Robotics, Machine Vision and Computational Linguistics
- Scheduling, Planning, Resource Allocation
- Temporal and Spatial Reasoning.
The talk will provide a brief introduction to this field, and to the
work of the UNH Constraint Computation Center. It will focus on one of
the field's key rese arch challenges: understanding and automating the
modeling process. Constraint p roblems are modeled as consisting of
variables, values and constraints; a soluti on assigns a value to each
variable subject to restrictions that the constraints impose on which
combinations of values are permitted. For example, the problem might
be to assign professors (values) to courses (variables), subject to
the co nstraints that courses that meet at the same time cannot be
taught by the same p rofessor. Automated modeling encompasses moving
from a problem stated in a form natural for the user to a
representation suitable for efficient processing by co nstraint
solving methods.
Biographical Information
Professor Freuder received his B.A. from Harvard and his Ph.D. from
M.I.T. He is a Fellow of the American Association for Artificial
Intelligence, the founding Editor-in-Chief of the Constraints journal,
and the Executive Chair of the Organ izing Committee of the
International Conference on Principles and Practice of Co nstraint
Programming. He is the Director of the UNH Constraint Computation
Cente r (http://www.cs.unh.edu/ccc).
Eyal Amir
Last modified: Wed Mar 3 16:54:13 PST 1999