This book constitutes the thoroughly refereed and extended post-proceedings of the 11th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2006, held in Caparica, Portugal in June 2006.
Besides papers taken from the workshop, others are submitted in response to an open call for papers after the workshop.
The 10 revised full papers presented together with a tutorial on hybrid algorithms were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on global constraints, search and heuristics, language and implementation issues, and modeling.
Author(s): Francisco Azevedo, Pedro Barahona, Francois Fages, Francesca Rossi
Series: Lecture Notes in Artificial Intelligence 4651
Edition: 1
Publisher: Springer
Year: 2007
Language: English
Pages: 191
Front matter......Page 1
Overview......Page 8
The Conceptual Model and the Design Model......Page 9
Mapping from the Conceptual to the Design Model......Page 10
Modelling Requirements for Constraint Solvers......Page 11
Constraints Which Propagate Domain Information......Page 12
Linear Constraints......Page 14
Propositional Clause Solvers and Set Solvers......Page 16
One-Way Constraints, or Invariants......Page 17
Communicating Solvers......Page 18
Channeling Constraints......Page 19
Propagation and Local Cuts......Page 21
Subproblems Handled with Independent Search Routines......Page 26
Context......Page 27
Overview......Page 28
Benefits of Search Hybridisation......Page 30
Loose Search Hybridisation......Page 31
Master-Slave Hybrids......Page 32
Complex Hybrids of Local and Constructive Search......Page 34
Summary......Page 36
Introduction......Page 40
Set Reasoning......Page 41
Steiner Triples......Page 42
Social Golfers......Page 43
Examples and Definitions......Page 45
Algorithm......Page 48
Results and Limitations......Page 49
Conclusions and Further Research......Page 52
References......Page 53
Introduction......Page 55
Motivation and Problem Description......Page 56
Double Precedence Graphs......Page 57
Constraint Model......Page 58
Constraint Model......Page 59
A Propagation Rule for Direct Precedences......Page 64
Sequence-Dependent Setup Times......Page 65
A Note on Open Graphs......Page 66
Experimental Results......Page 67
Conclusion......Page 68
References......Page 69
Introduction......Page 70
QCSPs......Page 72
Existential Analysis......Page 74
Functional Domain Analysis......Page 77
Look-Ahead Analysis......Page 79
Dual Analysis......Page 80
Experiments......Page 82
Conclusion......Page 83
Introduction......Page 85
Semiring-Based Soft Constraints......Page 87
Negative and Positive Preferences......Page 88
Bipolar Preference Structures......Page 89
Bipolar Preference Problems......Page 91
Positive Versus Negative Preferences......Page 92
Associativity of Preference Compensation......Page 93
Branch and Bound......Page 95
Bipolar Propagation......Page 96
Related and Future Work......Page 98
Introduction......Page 100
Preliminaries......Page 102
The PKC Model for Constraint Privacy......Page 103
Assignment Privacy on $DisFC$......Page 104
DisFC Versions......Page 105
Breaking Privacy......Page 107
The $DisFC_lies$ Algorithm......Page 108
Theoretical Results......Page 110
Privacy Improvements of $DisFC_lies$......Page 111
Experimental Results......Page 112
Conclusion......Page 114
Introduction......Page 115
Preliminaries......Page 117
Axiomatization of $T$......Page 118
Block and Quantified Block in $T$......Page 119
Basic Formula and Block in $T$......Page 120
Decomposition of Quantified Solved Blocks......Page 121
Working and General Solved Formulas......Page 123
Main Idea......Page 124
Rewriting Rules......Page 125
Conclusion......Page 129
Introduction......Page 131
Background......Page 133
Extracting Assignments......Page 134
Basic Algorithm......Page 135
Extracting Cyclic Assignments......Page 138
Extracting Microstructure......Page 142
Applications......Page 143
Conclusion......Page 144
Introduction......Page 146
Constraint Handling Rules......Page 147
Theory $\cal T$ of Finite or Infinite Trees......Page 148
The CHR Rational Tree Solver......Page 149
Term Order and Termination......Page 150
Exponential Complexity for Non-flat Equations......Page 153
Quadratic Complexity for Flat Equations......Page 155
Flattening Non-flat Equations in $\cal T$......Page 156
Reachable Variables and Equations......Page 157
The Solving Algorithm......Page 158
Conclusion......Page 159
Introduction......Page 161
Terminology......Page 162
The FC-EBJ Algorithm......Page 163
Recognizing Clustered Acyclic CSPs......Page 164
Recognizing Acyclic CSP Together with MAC......Page 169
Simplifying the Nogood Learning Procedure......Page 170
Experimental Evaluation......Page 171
Comparison of MAC-Based Algorithms......Page 172
Comparison of FC-Based Algorithms......Page 173
Conclusion......Page 174
Introduction......Page 176
A CP Model......Page 178
Computational Complexity......Page 180
Domain Pre-processing......Page 182
Cost-Based Filtering by Relaxation......Page 183
Experimental Results......Page 185
Conclusion......Page 188
Back matter......Page 191
