Principles of Constraint Programming

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780521825832 | 0521825830
Cover: Hardcover
Copyright: 9/15/2003

Rent

(Recommended)

$60.97

Term

Due

Price

Semester

Dec 13

$64.17

Quarter

Aug 16

$60.97

Short Term

Jul 18

$57.75

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping cart.
Buy New

Special Order: 1-2 Weeks

$87.67
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

$58.50

Constraints are everywhere: most computational problems can be described in terms of restrictions imposed on the set of possible solutions, and constraint programming is a problem-solving technique that works by incorporating those restrictions in a programming environment. It draws on methods from combinatorial optimization and artificial intelligence, and has been successfully applied in a number of fields from scheduling, computational biology, finance, electrical engineering and operations research through to numerical analysis. This textbook for upper-division students provides a thorough and structured account of the main aspects of constraint programming. The author provides many worked examples that illustrate the usefulness and versatility of this approach to programming, as well as many exercises throughout the book that illustrate techniques, test skills and extend the text. Pointers to current research, extensive historical and bibliographic notes, and a comprehensive list of references will also be valuable to professionals in computer science and artificial intelligence.

Acknowledgements

1 Introduction

(7)

1.1 Basic characteristics of constraint programming

(2)

1.2 Applications of constraint programming

(2)

1.3 A very short history of the subject

(1)

1.4 Our approach

(1)

1.5 Organisation of the book

(2)

2 Constraint satisfaction problems: examples

(46)

2.1 Basic concepts

(2)

2.2 Constraint satisfaction problems on integers

(5)

2.3 Constraint satisfaction problems on reals

(3)

2.4 Boolean constraint satisfaction problems

(2)

2.5 Symbolic constraint satisfaction problems

(22)

2.6 Constrained optimization problems

(4)

2.7 Summary

(1)

2.8 Exercises

(3)

2.9 Bibliographic remarks

(1)

2.10 References

(2)

3 Constraint programming in a nutshell

(28)

3.1 Equivalence of CSPs

(3)

3.2 Basic framework for constraint programming

(13)

3.2.1 PREPROCESS

(1)

3.2.2 RAPPY

(1)

3.2.3 ATOMIC

(1)

3.2.4 SPLIT

(3)

3.2.5 PROCEED BY CASES

(2)

3.2.6 CONSTRAINT PROPAGATION

(4)

3.2.7 Constraint propagation algorithms

(1)

3.3 Example: Boolean constraints

(3)

3.4 Example: polynomial constraints on integer intervals

(6)

3.5 Summary

(1)

3.6 Bibliographic remarks

(1)

4 Some complete constraint solvers

(53)

4.1 A proof theoretical framework

(9)

4.1.1 Proof rules

(8)

4.1.2 Derivations S

4.2 Term equations

(15)

4.2.1 Terms

(1)

4.2.2 Substitutions

(1)

4.2.3 Unifiers and mgus

(3)

4.2.4 Unification problem and solving of CSPs

(1)

4.2.5 The UNIF proof system

(4)

4.2.6 The MARTELLI-MONTANARI algorithm

103

(4)

4.3 Linear equations over reals

107

(14)

4.3.1 Linear expressions and linear equations

107

(3)

4.3.2 Substitutions, unifiers and mgus

110

(1)

4.3.3 Linear equations and CSPs

111

(1)

4.3.4 The LIN proof system

112

(3)

4.3.5 The GAUSS-JORDAN ELIMINATION algorithm

115

(3)

4.3.6 The GAUSSIAN ELIMINATION algorithm

118

(3)

4.4 Linear inequalities over reals

121

(10)

4.4.1 Syntax

121

(1)

4.4.2 Linear inequalities and CSPs

122

(1)

4.4.3 The INEQ proof system

123

(1)

4.4.4 The FOURIER-MOTZKIN ELIMINATION algorithm

124

(7)

4.5 Summary

131

(1)

4.6 Exercises

131

(1)

4.7 Bibliographic remarks

132

(1)

4.8 References

133

(2)

5 Local consistency notions

135

(43)

5.1 Node consistency

136

(2)

5.2 Arc consistency

138

(5)

5.3 Hyper-arc consistency

143

(1)

5.4 Directional arc consistency

144

(3)

5.5 Path consistency

147

(8)

5.6 Directional path consistency

155

(2)

5.7 k-consistency

157

(7)

5.8 Strong k-consistency

164

(2)

5.9 Relational consistency

166

(4)

5.10 Graphs and CSPs

170

(5)

5.11 Summary

175

(1)

5.12 Exercises

175

(1)

5.13 Bibliographic remarks

176

(1)

5.14 References

176

(2)

6 Some incomplete constraint solvers

178

(76)

6.1 A useful lemma

180

(1)

6.2 Equality and disequality constraints

181

(3)

6.3 Boolean constraints

184

(8)

6.3.1 Transformation rules

185

(1)

6.3.2 Domain reduction rules

186

(2)

6.3.3 Example: full adder circuit

188

(3)

6.3.4 A characterisation of the system BOOL

191

(1)

6.4 Linear constraints on integer intervals

192

(19)

6.4.1 Domain reduction rules for inequality constraints

194

(2)

6.4.2 Domain reduction rules for equality constraints

196

(3)

6.4.3 Rules for disequality constraints

199

(1)

6.4.4 Rules for strict inequality constraints

200

(1)

6.4.5 Shifting from intervals to finite domains

200

(1)

6.4.6 Example: the SEND + MORE = MONEY puzzle

201

(1)

6.4.7 Bounds consistency

202

(4)

6.4.8 A characterisation of the LINEAR EQUALITY rule

206

(5)

6.5 Arithmetic constraints on integer intervals

211

(13)

6.5.1 Domain reduction rules: first approach

211

(2)

6.5.2 Domain reduction rules: second approach

213

(4)

6.5.3 Domain reduction rules: third approach

217

(4)

6.5.4 Implementation of the third approach

221

(2)

6.5.5 Shifting from intervals to finite domains

223

(1)

6.6 Arithmetic constraints on reals

224

(18)

6.6.1 Interval arithmetic

226

(1)

6.6.2 Domain reduction rules

227

(6)

6.6.3 Implementation issues

233

(3)

6.6.4 Using floating-point intervals

236

(2)

6.6.5 Correctness and efficiency issues

238

(4)

6.7 Arithmetic equations over reals

242

(3)

6.8 Summary

245

(1)

6.9 Exercises

245

(3)

6.10 Bibliographic remarks

248

(3)

6.11 References

251

(3)

7 Constraint propagation algorithms

254

(45)

7.1 Generic iteration algorithms

256

(12)

7.1.1 Iterations

256

(5)

7.1.2 Algorithms for arbitrary partial orderings

261

(3)

7.1.3 Algorithms for cartesian products of partial orderings

264

(4)

7.2 From partial orderings to CSPs

268

(1)

7.3 A node consistency algorithm

269

(2)

7.4 An arc consistency algorithm

271

(2)

7.5 A hyper-arc consistency algorithm

273

(2)

7.6 A directional arc consistency algorithm

275

(2)

7.7 A path consistency algorithm

277

(4)

7.8 A directional path consistency algorithm

281

(2)

7.9 A k-consistency algorithm

283

(3)

7.10 A relational consistency algorithm

286

(1)

7.11 Implementations of incomplete constraint solvers

287

(3)

7.12 Summary

290

(1)

7.13 Exercises

291

(4)

7.14 Bibliographic remarks

295

(2)

7.15 References

297

(2)

8 Search

299

(52)

8.1 Search trees

301

(2)

8.2 Labeling trees

303

(10)

8.2.1 Complete labeling trees

304

(4)

8.2.2 Reduced labeling trees

308

(2)

8.2.3 prop labeling trees

310

(3)

8.3 An example: SEND + MORE = MONEY

313

(2)

8.4 Instances of prop labeling trees

315

(9)

8.4.1 Forward checking

315

(4)

8.4.2 Partial look ahead

319

(2)

8.4.3 Maintaining arc consistency (MAC)

321

(3)

8.5 Search algorithms for the labeling trees

324

(8)

8.5.1 Backtrack-free search

325

(2)

8.5.2 Backtrack-free search with constraint propagation

327

(2)

8.5.3 Backtracking

329

(1)

8.5.4 Backtracking with constraint propagation

330

(2)

8.6 Instances of backtracking with constraint propagation

332

(3)

8.6.1 Forward checking

332

(1)

8.6.2 Partial look ahead

333

(1)

8.6.3 Maintaining arc consistency (MAC)

334

(1)

8.6.4 Searching for all solutions

335

(1)

8.7 Search algorithms for finite constrained optimization problems

335

(6)

8.7.1 Branch and bound

337

(2)

8.7.2 Branch and bound with constraint propagation

339

(1)

8.7.3 Branch and bound with constraint propagation and cost constraint

339

(2)

8.8 Heuristics for search algorithms

341

(3)

8.8.1 Variable selection

341

(2)

8.8.2 Value selection

343

(1)

8.9 An abstract branch and bound algorithm

344

(3)

8.10 Summary

347

(1)

8.11 Exercises

347

(1)

8.12 Bibliographic remarks

348

(1)

8.13 References

349

(2)

9 Issues in constraint programming

351

(36)

9.1 Modeling

352

(7)

9.1.1 Choosing the right variables

352

(1)

9.1.2 Choosing the right constraints

353

(3)

9.1.3 Choosing the right representation

356

(2)

9.1.4 Global constraints

358

(1)

9.2 Constraint programming languages

359

(5)

9.2.1 Constraint logic programming

360

(2)

9.2.2 ILOG solver

362

(1)

9.2.3 Generation of constraints

363

(1)

9.3 Constraint propagation

364

(2)

9.4 Constraint solvers

366

(3)

9.4.1 Building constraint solvers

366

(1)

9.4.2 Incrementality

367

(1)

9.4.3 Simplification of constraints

368

(1)

9.5 Search

369

(10)

9.5.1 Search in modeling languages

369

(1)

9.5.2 Depth-first search: backtracking and branch and bound

370

(1)

9.5.3 Breadth-first search and limited discrepancy search

371

(1)

9.5.4 Local search

372

(3)

9.5.5 Search in constraint programming languages

375

(3)

9.5.6 Biology-inspired approaches

378

(1)

9.6 Over-constrained problems

379

(5)

9.6.1 Partial, weighted and fuzzy CSPs

380

(1)

9.6.2 Constraint hierarchies

381

(2)

9.6.3 Generalisations

383

(1)

9.6.4 Reified constraints

383

(1)

9.7 Summary

384

(1)

9.8 Bibliographic remarks

384

(3)

Bibliography

387

(14)

Author index

401

(3)

Subject index

404

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Principles of Constraint Programming

Summary

Table of Contents

Supplemental Materials