Principles of constraint programming / Krzysztof R. Apt.

Includes bibliographical references (p. 387-400) and indexes.

1 Introduction
1.1 Basic characteristics of constraint programming
1.2 Applications of constraint programming
1.3 A very short history of the subject
1.4 Our approach
1.5 Organisation of the book
2 Constraint satisfaction problems: examples
2.1 Basic concepts
2.2 Constraint satisfaction problems on integers
2.3 Constraint satisfaction problems on reals
2.4 Boolean constraint satisfaction problems
2.5 Symbolic constraint satisfaction problems
2.6 Constrained optimization problems
2.7 Summary
2.8 Exercises
2.9 Bibliographic remarks
2.10 References
3 Constraint programming in a nutshell
3.1 Equivalence of CSPs
3.2 Basic framework for constraint programming
3.2.1 PREPROCESS
3.2.2 HAPPY
3.2.3 ATOMIC
3.2.4 SPLIT
3.2.5 PROCEED BY CASES
3.2.6 CONSTRAINT PROPAGATION
3.2.7 Constraint propagation algorithms
3.3 Example: Boolean constraints
HAPPY
ATOMIC
SPLIT
CONSTRAINT PROPAGATION
PROCEED BY CASES
3.4 Example: polynomial constraints on integer intervals
PREPROCESS
ATOMIC
CONSTRAINT PROPAGATION
SPLIT
PROCEED BY CASES
3.5 Summary
3.6 Bibliographic remarks
4 Some complete constraint solvers
4.1 A proof theoretical framework
4.1.1 Proof rules
4.1.2 Derivations
4.2 Term equations
4.2.1 Terms
4.2.2 Substitutions
4.2.3 Unifiers and mgus
4.2.4 Unification problem and solving of CSPs
4.2.5 The UNIF proof system
4.2.6 The MARTELLI–MONTANARI algorithm
4.3 Linear equations over reals
4.3.1 Linear expressions and linear equations
4.3.2 Substitutions, unifiers and mgus
4.3.3 Linear equations and CSPs
4.3.4 The LIN proof system
4.3.5 The GAUSS–JORDAN ELIMINATION algorithm
4.3.6 The GAUSSIAN ELIMINATION algorithm
4.4 Linear inequalities over reals
4.4.1 Syntax
4.4.2 Linear inequalities and CSPs
4.4.3 The INEQ proof system
4.4.4 The Fourier–Motzkin Elimination algorithm
4.5 Summary
4.6 Exercises
4.7 Bibliographic remarks
4.8 References
5 Local consistency notions
5.1 Node consistency
5.2 Arc consistency
5.3 Hyper-arc consistency
5.4 Directional arc consistency
5.5 Path consistency
5.6 Directional path consistency
5.7 k-consistency
5.8 Strong k-consistency
5.9 Relational consistency
5.10 Graphs and CSPs
5.11 Summary
5.12 Exercises
5.13 Bibliographic remarks
5.14 References
6 Some incomplete constraint solvers
6.1 A useful lemma
6.2 Equality and disequality constraints
6.3 Boolean constraints
6.3.1 Transformation rules
6.3.2 Domain reduction rules
6.3.3 Example: full adder circuit
6.3.4 A characterisation of the system BOOL
6.4 Linear constraints on integer intervals
6.4.1 Domain reduction rules for inequality constraints
6.4.2 Domain reduction rules for equality constraints
6.4.4 Rules for strict inequality constraints
6.4.5 Shifting from intervals to finite domains
6.4.6 Example: the SEND + MORE = MONEY puzzle
6.4.7 Bounds consistency
6.4.8 A characterisation of the LINEAR EQUALITY rule
6.5 Arithmetic constraints on integer intervals
6.5.1 Domain reduction rules: first approach
6.5.2 Domain reduction rules: second approach
6.5.3 Domain reduction rules: third approach
6.5.4 Implementation of the third approach
6.5.5 Shifting from intervals to finite domains
6.6 Arithmetic constraints on reals
6.6.1 Interval arithmetic
6.6.2 Domain reduction rules
6.6.3 Implementation issues
6.6.4 Using floating-point intervals
6.6.5 Correctness and effciency issues
6.7 Arithmetic equations over reals
6.8 Summary
6.9 Exercises
6.10 Bibliographic remarks
6.11 References
7 Constraint propagation algorithms
7.1 Generic iteration algorithms
7.1.1 Iterations
7.1.2 Algorithms for arbitrary partial orderings
7.2 From partial orderings to CSPs
7.3 A node consistency algorithm
7.4 An arc consistency algorithm
7.5 A hyper-arc consistency algorithm
7.6 A directional arc consistency algorithm
7.7 A path consistency algorithm
7.8 A directional path consistency algorithm
7.9 A k-consistency algorithm
7.10 A relational consistency algorithm
7.11 Implementations of incomplete constraint solvers
7.12 Summary
7.13 Exercises
7.14 Bibliographic remarks
7.15 References
8 Search
8.1 Search trees
8.2 Labeling trees
8.2.1 Complete labeling trees
8.2.2 Reduced labeling trees
8.2.3 prop labeling trees
8.3 An example: SEND + MORE = MONEY
8.4 Instances of prop labeling trees
8.4.1 Forward checking
8.4.2 Partial look ahead
8.4.3 Maintaining arc consistency (MAC)
8.5 Search algorithms for the labeling trees
8.5.1 Backtrack-free search
8.5.2 Backtrack-free search with constraint propagation
8.5.3 Backtracking
8.5.4 Backtracking with constraint propagation
8.6 Instances of backtracking with constraint propagation
8.6.1 Forward checking
8.6.2 Partial look ahead
8.6.3 Maintaining arc consistency (MAC)
8.6.4 Searching for all solutions
8.7 Search algorithms for finite constrained optimization problems
8.7.1 Branch and bound
8.7.2 Branch and bound with constraint propagation
8.7.3 Branch and bound with constraint propagation and cost constraint
8.8 Heuristics for search algorithms
8.8.1 Variable selection
8.8.2 Value selection
8.9 An abstract branch and bound algorithm
8.10 Summary
8.11 Exercises
8.12 Bibliographic remarks
8.13 References
9 Issues in constraint programming
9.1 Modeling
9.1.1 Choosing the right variables
9.1.2 Choosing the right constraints
9.1.3 Choosing the right representation
9.1.4 Global constraints
9.2 Constraint programming languages
9.2.1 Constraint logic programming
9.2.2 ILOG solver
9.2.3 Generation of constraints
9.3 Constraint propagation
9.4 Constraint solvers
9.4.1 Building constraint solvers
9.4.2 Incrementality
9.4.3 Simplification of constraints
9.5 Search
9.5.1 Search in modeling languages
9.5.2 Depth-first search: backtracking and branch and bound
9.5.3 Breadth-first search and limited discrepancy search
9.5.4 Local search
9.5.5 Search in constraint programming languages
9.5.6 Biology-inspired approaches
9.6 Over-constrained problems
9.6.1 Partial, weighted and fuzzy CSPs
9.6.2 Constraint hierarchies
9.6.3 Generalisations
9.6.4 Reified constraints
9.7 Summary
9.8 Bibliographic remarks
Bibliography
Author index
Subject index