![]() |
|||
![]()
|
![]() |
![]() |
![]() |
Chapter 17
|
1. | Introduction | ||
2. | History | ||
2.1. | Declarative Modeling and Efficient Enforcement | ||
2.1.1. | Algorithm = Logic + Control | ||
2.1.2. | Constraints for Multidirectional Programming | ||
2.1.3. | Constraint Logic Programming | ||
2.2. | Propagation | ||
2.2.1. | Early Applications | ||
2.2.2. | Constraint Satisfaction Problems | ||
2.2.3. | Constraint Propagation in Logic Programming | ||
2.3. | Search | ||
3. | Programming with a Constraint Store | ||
3.1. | Primitive Constraints | ||
3.2. | CLP ([curly R]) | ||
4. | Constraint Propagation | ||
4.1. | Propagating Changes | ||
4.2. | Active Constraints | ||
4.2.1. | Propagating New Information | ||
4.2.2. | Constraint Agents | ||
4.2.3. | Some Built-In Constraint Agents | ||
4.3. | Map Coloring | ||
4.3.1. | The Map Coloring Program | ||
4.4. | Building Constraint Agents | ||
4.4.1. | Guards | ||
4.4.2. | Agents Defined by Specific Codes | ||
5. | Implementation and Applications | ||
5.1. | Constraints Embedded in A Host Programming Language | ||
5.1.1. | Control | ||
5.1.2. | Concurrency | ||
5.1.3. | Logic Programming as a Host Language | ||
5.1.4. | Libraries for Embedded Constraint Programming | ||
5.2. | Applications of Constraint Programming | ||
6. | Current Developments | ||
6.1. | Constraints in the Computing Environment | ||
6.2. | Mixed Initiative Programming | ||
6.3. | Interval Reasoning | ||
6.4. | Stochastic Techniques | ||
References |
Constraint programming is a paradigm that is tailored to hard search problems. To date the main application areas are those of planning, scheduling, timetabling, routing, placement, investment, configuration, design, and insurance. Constraint programming incorporates techniques from mathematics, artificial intelligence, and operations research, and it offers significant advantages in these areas since it supports fast program development, economic program maintenance, and efficient runtime performance. The direct representation of the problem, in terms of constraints, results in short, simple programs that can be easily adapted to changing requirements. The integration of these techniques into a coherent high-level language enables the programmer to concentrate on choosing the best combination for the problem at hand. Because programs are quick to develop and to modify, it is possible to experiment with ways of solving a problem until the best and fastest program has been found. Moreover, more complex problems can be tackled without the programming task becoming unmanageable. A tutorial introduction to constraint logic programming can be found in Frühwirth et al. (1992).
Constraint logic programming (CLP) combines logic, which is used to specify a set of possibilities explored via a very simple inbuilt search method, with constraints, which are used to minimize the search by eliminating impossible alternatives in advance. The programmer can state the factors that must be taken into account in any solution -- the constraints, state the possibilities-- the logic program, and use the system to combine reasoning and search. The constraints are used to restrict and guide search.
The whole field of software research and development has one aim, viz. to optimize the task of specifying and writing and maintaining correct, functioning programs. Three important factors to be optimized are:
Constraint programming is, perhaps, unique in making a direct contribution in all three areas. This is why it is such an exciting paradigm.
In 1963, Sutherland introduced the Sketchpad system, a constraint language for graphical interaction. Other early constraint programming languages were Fikes' Ref-Arf, Lauriere's Alice, Sussmann's CONSTRAINTS, and Borning's ThingLab. These languages already offered the most important features of constraint programming: declarative problem modeling and efficient constraint enforcement; propagation of the effects of decisions; flexible and intelligent search for feasible solutions. Each of these three features has been the study of extensive research over a long period.
The current flowering of constraint programming owes itself to a generation of languages in which declarative modeling, constraint propagation, and explicit search control are supported in a coherent architecture that makes them easy to understand, combine, and apply.
Previous | Table of Contents | Next |
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |