Constraint Processing

Rina Dechter

• Publisher: Morgan Kaufmann
• Year: 2003
• Print ISBN: 9781558608900
• eBook ISBN: 9780080502953
• Topic: Computer Science
• Subtopic: Artificial Intelligence (AI) & Semantics
• Index: Computer Science

Constraint satisfaction is a simple but powerful tool. Constraints identify the impossible and reduce the realm of possibilities to effectively focus on the possible, allowing for a natural declarative formulation of what must be satisfied, without expressing how. The field of constraint reasoning has matured over the last three decades with contributions from a diverse community of researchers in artificial intelligence, databases and programming languages, operations research, management science, and applied mathematics. Today, constraint problems are used to model cognitive tasks in vision, language comprehension, default reasoning, diagnosis, scheduling, temporal and spatial reasoning. In Constraint Processing, Rina Dechter, synthesizes these contributions, along with her own significant work, to provide the first comprehensive examination of the theory that underlies constraint processing algorithms. Throughout, she focuses on fundamental tools and principles, emphasizing the representation and analysis of algorithms.- Examines the basic practical aspects of each topic and then tackles more advanced issues, including current research challenges- Builds the reader's understanding with definitions, examples, theory, algorithms and complexity analysis- Synthesizes three decades of researchers work on constraint processing in AI, databases and programming languages, operations research, management science, and applied mathematics

chapter 1

Introduction

The work under our labour grows luxurious by restraint.

John Milton, Paradise Lost

We regularly encounter constraint in our day-to-day lives—for instance, a finite amount of memory in our PCs, seats in the car, hours in the day, money in the bank. And we regularly engage in solving constraint satisfaction problems: how to live well but within our means, how to eat healthy but still enjoy food. Most of the time, we don’t require sophisticated computer-processed algorithms to figure out whether to splurge on a ski vacation or eat the triple-layer chocolate cake. But consider the complexity encountered when the number of constraints to be satisfied, and variables involved, begins to grow. For example, we find it takes a surprisingly long time to determine the optimal seating arrangement for a dinner party, or choose one movie rental for a large group of friends.

Now imagine the difficulty in scheduling classrooms for a semester of university instruction. We need to allocate a classroom for every course while simultaneously satisfying the constraints that no two classes may be held in the same classroom at the same time, no professor can teach in two different classrooms at the same time, no class may be scheduled in the middle of the night, all classes must be offered in appropriately sized rooms or lecture halls, certain classes must not be scheduled at the same time, and so on.

As the complexity of the problem grows, we turn to computers to help us find an acceptable solution. Computer scientists have devised language to model constraint satisfaction problems and have developed methods for solving them. The language of constraints is used to model simple cognitive tasks such as vision, language comprehension, default reasoning and abduction, as well as tasks that require high levels of human expertise such as scheduling, design, diagnosis, and temporal and spatial reasoning.

In general, the tasks posed in the language of constraints are computationally intractable (NP-hard), which means that you cannot expect to design algorithms that scale efficiently with the problem size, in all cases. However, it is possible and desirable to identify special properties of a problem class that can accommodate efficient solutions and to develop general algorithms that are efficient for as many problems as possible.

Indeed, over the last two to three decades, a great deal of theoretical and experimental research has focused on developing and improving the performance of general algorithms for solving constraint satisfaction problems, on identifying restricted subclasses that can be solved efficiently, called tractable classes, and on developing approximation algorithms. This book describes the theory and practice underlying such constraint processing methods.

The remainder of this chapter is divided into three parts. First is an informal overview of constraint networks, starting with common examples of problems that can be modeled as constraint satisfaction problems. Second is an overview of the book by chapter. Third is a review of mathematical concepts and some preliminaries relevant to our discussion throughout the book.

1.1 Basic Concepts and Examples

In general, constraint satisfaction problems include two important components of variables with associated domains and constraints. Let’s define each component and then take a look at several examples that formally model constraint satisfaction problems. First, every constraint problem must include variables: objects or items that can take on a variety of values. The set of possible values for a given variable is called its domain. For example, in trying to find an acceptable seating arrangement for a dinner party, we may choose to see the chairs as our variables, each with the same domain, which is the list of all guests.

The second component to every constraint problem is the set of constraints themselves. Constraints are rules that impose a limitation on the values that a variable, or a combination of variables, may be assigned. If the host and hostess must sit at the two ends of the table, then their choices of seats are constrained. If two feuding guests must not be placed next to or directly opposite one another, then we must include this constraint in our overall problem statement.

Note that there is often more than one way to model a problem. In the previous example, we could just as logically have decided to call the guests our variables and their domains the set of chairs at the table. In this case, assuming a one-to-one correspondence between chairs and guests, the choice makes little difference, but in other cases, one formulation of a problem may lend itself more readily to solution techniques than another.

A model that includes variables, their domains, and constraints is called a constraint network, also called a constraint problem. Use of the term “network” can be traced to the early days of constraint satisfaction work when the research focus was restricted to sets of constraints whose dependencies were naturally captured by simple graphs. We prefer this term because it emphasizes the importance of a constraint dependency structure in reasoning algorithms.

A solution is an assignment of a single value from its domain to each variable such that no constraint is violated. A problem may have one, many, or no solutions. A problem that has...

Table of contents

• Cover image
• Title page
• Table of Contents
• AUTHOR BIOGRAPHY
• Copyright
• Foreword
• Dedication
• Preface
• Chapter 1: Introduction
• Part I: Basics of Constraint Processing
• Part II: Advanced Methods
• Bibliography
• Index