Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


Chapter 17
Constraint Programming

Mark Wallace


CONTENTS

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

1. INTRODUCTION

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:

  • Correctness of programs
  • Clarity and brevity of programs
  • Efficiency of programs

Constraint programming is, perhaps, unique in making a direct contribution in all three areas. This is why it is such an exciting paradigm.

2. HISTORY

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

footer nav
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.