Principles and Practice of Constraint Programming-CP97: Third International Conference, CP97 Linz, Austria, October 29 – November 1, 1997 Proceedings

Pascal Van Hentenryck (auth.), Gert Smolka (eds.)9783540637530, 3540637532

This book constitutes the refereed proceedings of the Third International Conference on Principles and Practice of Constraint Programming, CP’97, held in Linz, Austria in October/November 1997.
The volume presents 37 revised full papers carefully selected from a total of 132 submissions; also included are the abstracts of two invited talks and three tutorials. The papers address all current aspects of constraint programming. Among the topics covered are constraint matching, constraint languages, set constraints, constraint search, constraint satisfaction problems, scheduling, constraint routing, temporal constraints, constraint graphs, local search, object-oriented constraint programming, etc.

---

Table of contents :
Visual Solver A modeling language for constraint programming….Pages 1-1
Narrowing a 2 n -block of sortings in O ( n log n )….Pages 2-16
Solving various weighted matching problems with constraints….Pages 17-31
A filtering algorithm for global sequencing constraints….Pages 32-46
Semantics and expressive power of a timed concurrent constraint language….Pages 47-61
Solving classes of set constraints with tree automata….Pages 62-76
The logic of search algorithms: Theory and applications….Pages 77-91
Verification of parallel systems using constraint programming….Pages 92-106
Random constraint satisfaction: A more accurate picture….Pages 107-120
Heavy-tailed distributions in combinatorial search….Pages 121-135
Counting, structure identification and maximum consistency for binary constraint satisfaction problems….Pages 136-149
Statistical analysis of backtracking on inconsistent CSPs….Pages 150-162
Using constraint propagation for complex scheduling problems: Managing size, complex resources and travel….Pages 163-166
Understanding and improving the MAC algorithm….Pages 167-181
Modelling exceptionally hard constraint satisfaction problems….Pages 182-195
Tabu search for maximal constraint satisfaction problems….Pages 196-208
Reconfigurable architectures: A new vision for optimization problems….Pages 209-221
Distributed partial constraint satisfaction problem….Pages 222-236
Localizer A modeling language for local search….Pages 237-251
Operational semantics and confluence of constraint propagation rules….Pages 252-266
AC-unification of higher-order patterns….Pages 267-281
On the complexity of unification and disunification in commutative idempotent semigroups….Pages 282-296
Ordering constraints over feature trees….Pages 297-311
From restricted path consistency to max-restricted path consistency….Pages 312-326
The constrainedness of Arc consistency….Pages 327-340
Look-ahead versus look-back for satisfiability problems….Pages 341-355
Why adding more constraints makes a problem easier for hill-climbing algorithms: Analyzing landscapes of CSPs….Pages 356-370
Interval methods for non-linear constraints….Pages 371-371
Configurable solvers: Tailoring general methods to specific applications….Pages 372-374
Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems….Pages 375-389
Five pitfalls of empirical scheduling research….Pages 390-404
Bounding the optimum of constraint optimization problems….Pages 405-419
GENIUS-CP: A generic single-vehicle routing algorithm….Pages 420-434
Satisfiability of quantitative temporal constraints with multiple granularities….Pages 435-449
Tractable recursion over geometric data….Pages 450-462
Finding solvable subsets of constraint graphs….Pages 463-477
Tractable disjunctive constraints….Pages 478-490
Compiling constraint solving using projection….Pages 491-505
Oscillation, heuristic ordering and pruning in neighborhood search….Pages 506-518
Programming constraint inference engines….Pages 519-533
NeMo+: Object-oriented constraint programming environment based on subdefinite models….Pages 534-548
Set constraints: A pearl in research on constraints….Pages 549-561