Tags
Language
Tags
March 2024
Su Mo Tu We Th Fr Sa
25 26 27 28 29 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 1 2 3 4 5 6

"Principles of Constraint Programming" by Krzysztof Apt

Posted By: exLib
"Principles of Constraint Programming" by Krzysztof Apt

"Principles of Constraint Programming" by Krzysztof Apt
Саmbridge University Press | 2003 | ISBN: 0521125499 0511062494 9780521125499 | 420 pages | PDF | 2 MB

This book meets the need for a modern, multidisciplinary introduction to the field that covers foundations and applications. Written by Krzysztof Apt, an authority on the subject, it will be welcomed by graduate students and professionals. With the insertion of constraint techniques into programming environments, new developments have accelerated the solution process.




Scheduling, vehicle routing and timetabling are all examples of constraint problems, and methods to solve them rely on the idea of constraint propagation and search.
Constraint programming combines ideas from artificial intelligence, programming languages, databases, and operational research.

Contents
Acknowledgements
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
3.4 Example: polynomial constraints on integer intervals
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.3 Rules for disequality 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 efficiency 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.1.3 Algorithms for cartesian products of 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
with TOC BookMarkLinks