Constraint Satisfaction Problems (PDF)

A Constraint Satisfaction Problem (CSP) consists of a set of
variables, a domain of values for each variable and a set of
constraints. The objective is to assign a value for each variable
such that all constraints are satisfied. CSPs continue to receive
increased attention because of both their high complexity and their
omnipresence in academic, industrial and even real-life problems.
This is why they are the subject of intense research in both
artificial intelligence and operations research. This book
introduces the classic CSP and details several
extensions/improvements of both formalisms and techniques in order
to tackle a large variety of problems. Consistency, flexible,
dynamic, distributed and learning aspects are discussed and
illustrated using simple examples such as the n-queen problem.

Contents

1. Foundations of CSP.

2. Consistency Reinforcement Techniques.

3. CSP Solving Algorithms.

4. Search Heuristics.

5. Learning Techniques.

6. Maximal Constraint Satisfaction Problems.

7. Constraint Satisfaction and Optimization Problems.

8. Distibuted Constraint Satisfaction Problems.

About the Authors

Khaled Ghedira is the general managing director of the Tunis
Science City in Tunisia, Professor at the University of Tunis, as
well as the founding president of the Tunisian Association of
Artificial Intelligence and the founding director of the SOIE
research laboratory. His research areas include MAS, CSP, transport
and production logistics, metaheuristics and security in
M/E-government. He has led several national and international
research projects, supervised 30 PhD theses and more than 50
Master's theses, co-authored about 300 journal, conference
and book research papers, written two text books on metaheuristics
and production logistics and co-authored three others.