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

# Programming with constraints

## an introduction

• 0 Ratings

#### — 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.

Previews available in: English

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

## 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 1998 by MIT Press in Cambridge, Mass.

 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

Author
Peter J. Stuckey

### ID Numbers

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