This book constitutes the thoroughly refereed and extended post-proceedings of the Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, held in Uppsala, Sweden in June 2005.
Besides papers taken from the workshop, others are submitted in response to an open call for papers after the workshop.
The 12 revised full papers presented 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): Brahim Hnich, Mats Carlsson, Francois Fages, Francesca Rossi
Series: Lecture Notes in Artificial Intelligence 3978
Edition: 1
Publisher: Springer
Year: 2006
Language: English
Pages: 186
Front matter......Page 1
Introduction......Page 8
Beyond Integer Variables......Page 9
$ c{All-Different}$ on Sets......Page 11
$ c{All-Different}$ on Tuples......Page 14
$ c{All-Different}$ on Multi-sets......Page 15
Global Cardinality Constraint......Page 16
Experiments......Page 17
Conclusions......Page 19
Introduction......Page 21
Syntax of CHR......Page 22
Declarative Semantics of CHR......Page 23
Operational Semantics of CHR......Page 24
The Lexicographic Order Constraint Solver......Page 25
Confluence......Page 26
Logical Correctness......Page 28
Worst-Case Time Complexity......Page 29
Completeness......Page 31
Implementation Experiments......Page 32
Conclusions......Page 33
Introduction......Page 36
Formal Background......Page 37
Among Constraint......Page 38
Common Constraint......Page 42
Disjoint Constraint......Page 43
Among Constraint......Page 45
Disjoint Constraint......Page 47
Conclusions......Page 48
Introduction......Page 51
Preliminaries......Page 54
Partitioning and Colouring Problems......Page 55
$k$-Colouring Algorithm......Page 56
Max Ind $k$-Colouring Algorithm......Page 59
Max Value $k$-Colouring......Page 60
Max $k$-COL and #Max $k$-COL Algorithms......Page 63
Introduction......Page 66
Preliminaries......Page 67
The 2FC Algorithm......Page 69
Theoretical Analysis......Page 72
Experimental Evaluation......Page 74
Discussion......Page 77
Introduction......Page 80
Description of Methods......Page 81
Heuristic Combinations Based on Weighted Sums......Page 83
Factor Analysis of Heuristic Performance......Page 86
Resumé of Factor Analysis......Page 87
Factor Patterns for CSP Heuristics and Their Interpretation......Page 88
Synergies with MAC......Page 89
Synergies with FC......Page 90
Assessment of Weighted-Sum Strategies in Terms of Heuristic Policies......Page 91
Limits to Synergy?......Page 92
Conclusions......Page 93
Introduction......Page 95
The FC, FC-CBJ Algorithms, and FF Ordering Heuristic......Page 96
Complexity of Backtrack Algorithms......Page 99
FC-CBJ Combined with FF Has $O*((d-1)^n)$ Complexity......Page 100
Both FC with FF and FC-CBJ Have a Complexity Greater Than $O*((d-1)^n)$......Page 103
Conclusion......Page 106
Introduction......Page 107
Preliminaries on CHR......Page 108
Syntax......Page 109
Operational Semantics......Page 110
CLP+CHR......Page 111
Assumptions About the Type System of the Host Language......Page 112
Type System for CHR......Page 113
Integration with CLP......Page 115
Type Structure......Page 116
Type System for CLP+CHR......Page 117
Typing of Polymorphic CHR Constraints......Page 119
Experimental Results......Page 120
Conclusion......Page 122
Introduction......Page 125
Constraint Programming Systems......Page 126
Variable Views with Value Operations......Page 127
Domain Operations and Range Iterators......Page 131
Variable Views with Domain Operations......Page 134
Views for Set Constraints......Page 135
Implementation......Page 136
Analysis and Evaluation......Page 137
Conclusion and Future Work......Page 138
Introduction......Page 140
Stochastic Constraint Programming......Page 141
Benders Decomposition......Page 142
Independent Subproblems......Page 143
Complete and Partial Master Problems......Page 144
An Illustrative Example: News Vendor Problem......Page 145
Stochastic Capacitated Warehouse Location Problem......Page 147
Stochastic Template Design Problem......Page 151
Conclusion......Page 153
Introduction......Page 156
Formal Background and Prerequisites......Page 157
Weak Symmetry Definition......Page 159
An Example: Magic Square Problem......Page 160
Theoretical Idea......Page 161
Modelling Approach......Page 162
Related Work......Page 164
Weak Symmetry Modelling of the Problem......Page 165
Experimental Results......Page 166
Conclusions of the Results......Page 167
Conclusions and Outlook......Page 169
Introduction......Page 171
Quasigroups and Latin Squares......Page 172
Quasigroup Completion Problem......Page 173
Quasigroups with Holes......Page 175
Original Generator......Page 176
Reformulated Generator......Page 178
Generator Quality......Page 179
Generator Efficiency......Page 183
Conclusions......Page 184
References......Page 185
Back matter......Page 186
