Cover of: Programming with constraints | Kim Marriott
Last edited by ImportBot
August 19, 2020 | History
An edition of Programming with constraints (1998)

Programming with constraints

an introduction

  • 0 Ratings
  • 1 Want to read
  • 0 Currently reading
  • 0 Have read

This edition was published in by MIT Press in Cambridge, Mass.

Written in English

467 pages

A comprehensive, self-contained introduction to constraint programming, in which programs are represented as relational equations between values and variables, and execution consists of assigning values to the variables that maintain the relational equations.

Read more

Previews available in: English

Edition Availability
Cover of: Programming with constraints
Programming with constraints: an introduction
1998, MIT Press
Hardcover in English

Add another edition?

Programming with constraints

First published in 1998



Work Description

A comprehensive, self-contained introduction to constraint programming, in which programs are represented as relational equations between values and variables, and execution consists of assigning values to the variables that maintain the relational equations.

Programming with constraints

an introduction

This edition was published in by MIT Press in Cambridge, Mass.


Table of Contents

Table of Contents vii
Preface xi
Introduction 1
Notes 6
I Constraints 9
1 Constraints 11
1.1 Constraints and Valuations 11
1.2 Modelling with Constraints 15
1.3 Constraint Satisfaction 18
1.4 Tree Constraints 22
1.5 Other Constraint Domains 27
1.6 Properties of Constraint Solvers 33
1.7 (*) Determined Variables and Local Propagation 35
1.8 Summary 41
1.9 Exercises 42
1.10 Practical Exercises 43
1.11 Notes 47
2 Simplification, Optimization and Implication 51
2.1 Constraint Simplification 51
2.2 Projection 53
2.3 Constraint Simplifiers 57
2.4 Optimization 61
2.5 The Simplex Algorithm 63
2.6 (*) Canonical Form Simplifiers 72
2.7 (*) Implication and Equivalence 75
2.8 Summary 78
2.9 Exercises 79
2.10 Practical Exercises 80
2.11 Notes 83
3 Finite Constraint Domains 85
3.1 Constraint Satisfaction Problems 86
3.2 A Simple Backtracking Solver 88
3.3 Node and Arc Consistency 91
3.4 Bounds Consistency 97
3.5 Generalized Consistency 109
3.6 Optimization for Arithmetic CSPs 114
3.7 Summary 120
3.8 Exercises 122
3.9 Practical Exercises 123
3.10 Notes 127
II Constraint Logic Programming 131
4 Constraint Logic Programs 133
4.1 User-Defined Constraints 137
4.2 Programming with Rules 140
4.3 Evaluation 143
4.4 Derivation Trees and Finite Failure 146
4.5 Goal Evaluation 149
4.6 Simplified Derivation Trees 151
4.7 The CLP Scheme 153
4.8 (*) Independence from Rule Ordering and Literal Selection 158
4.9 Summary 158
4.10 Exercises 158
4.11 Practical Exercises 160
4.12 Notes 164
5 Simple Modelling 167
5.1 Simple Modelling 167
5.2 Modelling Choice 169
5.3 Iteration 174
5.4 Optimization 179
5.5 Summary 181
5.6 Practical Exercises 181
5.7 Notes 184
6 Using Data Structures 185
6.1 Records 186
6.2 Lists 188
6.3 Association Lists 193
6.4 Binary Trees 198
6.5 Hierarchical Modelling 201
6.6 Tree Layout 203
6.7 Summary 208
6.8 Practical Exercises 208
6.9 Notes 211
7 Controlling Search 213
7.1 Estimating the Efficiency of a CLP Program 213
7.2 Controlling Search: An Example 217
7.3 Rule Ordering 220
7.4 Literal Ordering 220
7.5 Adding Redundant Constraints 223
7.6 Minimization 227
7.7 Identifying Deterministic Subgoals 230
7.8 An Extended Example: Bridge Building 235
7.9 Summary 246
7.10 Exercises 247
7.11 Practical Exercises 248
7.12 Notes 250
8 Modelling with Finite Domain Constraints 251
8.1 Domains and Labelling 252
8.2 Complex Constraints 256
8.3 Labelling 258
8.4 Different Problem Modellings 266
8.5 An Extended Example: Scheduling 272
8.6 (*) Arc Consistency 281
8.7 (*) Library Predicates 284
8.8 Summary 285
8.9 Practical Exercises 286
8.10 Notes 291
9 Advanced Programming Techniques 293
9.1 Extending the Constraint Solver 293
9.2 Combined Symbolic and Arithmetic Reasoning 298
9.3 Programming Optimization 301
9.4 Higher-order Predicates 307
9.5 Negation 309
9.6 CLP Languages with Dynamic Scheduling 313
9.7 (*) Meta Programming 320
9.8 (*) Library Predicates 324
9.9 Summary 342
9.10 Practical Exercises 343
9.11 Notes 346
10 CLP Systems 349
10.1 Simple Backtracking Goal Evaluation 349
10.2 Incremental Constraint Solving 352
10.3 Efficient Saving and Restoring of the Constraint Store 358
10.4 Implementing If-Then-Else, Once and Negation 361
10.5 Optimization 366
10.6 Other Incremental Constraint Solvers 369
10.7 (*) Incremental Real Arithmetic Solving 376
10.8 Summary 385
10.9 Exercises 385
10.10 Notes 387
III Other Constraint Programming Languages 389
11 Constraint Databases 391
11.1 Modelling with Constraint Databases 391
11.2 Bottom Up Evaluation 395
11.3 Bottom-Up versus Top-Down 405
11.4 Mimicking Top-Down Evaluation Bottom-Up 407
11.5 (*) Improving Termination 412
11.6 (*) Relationship with Relational Databases 416
11.7 Summary 421
11.8 Exercises 422
11.9 Practical Exercises 422
11.10 Notes 423
12 Other Constraint Programming Languages 425
12.1 The CLP Paradigm 425
12.2 Concurrent Constraint Programming Languages 427
12.3 Constraint Handling Rules 430
12.4 Functional Languages 433
12.5 Term Rewriting 436
12.6 Imperative Programming Languages 439
12.7 Constraint Solving Toolkits 440
12.8 Mathematical Languages 443
12.9 Notes 447
References 449
Index 459

Edition Notes

Includes bibliographical references and index.

Classifications

Dewey Decimal Class
005.13
Library of Congress
QA76.63 .M37 1998, QA76.63.M37 1998

Contributors

Author
Peter J. Stuckey

ID Numbers

Open Library
OL693300M
Internet Archive
programmingwithc00marr
ISBN 10
0262133415
LC Control Number
97040549
Library Thing
294308
Goodreads
4922386

Lists containing this Book

History

Download catalog record: RDF / JSON
August 19, 2020 Edited by ImportBot import existing book
August 4, 2020 Edited by ImportBot import existing book
February 22, 2011 Edited by 173.70.123.67 added description
April 28, 2010 Edited by Open Library Bot Linked existing covers to the work.
December 10, 2009 Created by WorkBot add works page