Recent advances in constraints : joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, Uppsala, Sweden, June 20-22, 2005 : revised selected and invited papers

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

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.