Recent Advances in Constraints: Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2004, Lausanne,

Titelei......Page 1
Preface......Page 5
Organization......Page 7
Table of Contents......Page 9
1 Introduction......Page 11
1.2 SWC = 2×GCC?......Page 12
1.4 Filtering for the SWC Constraint......Page 13
2 An Arc-Consistency Algorithm for SWC......Page 14
3 A Bound-Consistency Algorithm for SWC with [0, 1] Cardinalities......Page 17
References......Page 21
1 Introduction......Page 22
2 Bilattices......Page 23
3 Bilattice-Based CSPs......Page 26
4 Instances of the Framework and Applications......Page 28
4.1 Open Constraints......Page 29
4.2 An Import Operator......Page 32
4.3 Reconciliation of Multiple Agents Opinions......Page 33
5 Conclusion......Page 34
References......Page 35
1 Introduction......Page 36
2 Preliminaries......Page 37
3 Equally Constrained Variables and Responsibility Sets......Page 38
4.1 Maintaining Responsibility Sets......Page 40
4.2 Pruning Procedure of Algorithm FC-CBJ-EQ......Page 41
4.3 Correctness......Page 43
5 Experimental Evaluation......Page 45
5.1 Graph k-Coloring Problems......Page 46
5.2 Restricted Subgraph Isomorphism Problem......Page 47
6 Conclusion......Page 48
References......Page 49
1 Introduction......Page 51
2 Trying Harder to Fail First (1998)......Page 52
3.2 The Fail-First Principle......Page 54
3.3 Measuring the Ability to Fail-First as Branch Depth Minimization......Page 55
4.1 Fail-First with Forward Checking......Page 56
4.2 Tests with MAC......Page 58
4.3 The Impact of Promise......Page 59
5 The Proper Measure of Fail-Firstness......Page 60
6 Conclusions......Page 63
References......Page 65
1 Introduction......Page 66
2 GTA Assignment Problem......Page 67
2.1 Heuristic Backtrack Search......Page 68
2.3 Multi-agent Search......Page 69
3 Randomized BT Search with Restarts......Page 70
3.2 Randomization and Dynamic Geometric Restarts......Page 71
4 Experiments and Results......Page 72
4.2 Influence of the Ratio r......Page 74
4.3 Relative Performance of BT, LS, ERA, RGR, and RDGR......Page 75
5 Conclusions and Future Work......Page 78
References......Page 79
1 Introduction......Page 81
2 RelatedWork......Page 82
3 Preliminaries......Page 83
The Distributed BackJumping Procedure......Page 84
The Dynamic Value and Variable Ordering Heuristics......Page 85
Detailed Algorithm Description......Page 86
5 Soundness, Completeness and Termination......Page 89
6 Experimental Results......Page 90
7 Conclusion......Page 94
References......Page 95
1 Introduction......Page 96
2.1 Formalization......Page 97
3 RelatedWork......Page 98
4.2 Preamble......Page 99
4.3 Standard Distributed Breakout Applied......Page 100
4.4 DBA-VO......Page 101
4.6 Discussion......Page 102
5 Evaluation......Page 104
6 Conclusions and Future Work......Page 106
References......Page 107
1 Introduction......Page 108
2 Background and Previous Work......Page 110
3 Symmetry Detection......Page 111
4 More Comprehensive Symmetry Breaking......Page 114
5 Empirical Results......Page 115
6 Conclusion......Page 119
References......Page 120
Appendix: Compilation into SAT/0-1 ILP......Page 121
1 Introduction......Page 123
2 Background......Page 124
3 Hinge+ Decomposition (HINGE+)......Page 126
4 Cut Decomposition (CUT)......Page 128
5 Traverse Decomposition (TRAVERSE)......Page 129
7 Characterization......Page 131
8 Preliminary Experiments......Page 135
References......Page 137
1 Introduction......Page 138
2.1 Constraint Satisfaction Problems......Page 140
2.3 Hamming Distance of CSPs......Page 141
3 Algorithm for Max Hamming Distance (2, 2)-CSP......Page 142
4 Algorithm for Max Hamming Distance (d, l)-CSP......Page 148
References......Page 151
1 Introduction......Page 152
2 The GSTP Architecture......Page 154
2.2 The GSTP Client......Page 155
3.1 Basic Notions......Page 156
3.2 A Strategy to Solve GSTP......Page 158
3.3 The AC-G Algorithm......Page 159
4 Implementation and Experimental Results......Page 160
4.1 Technologies and Optimizations......Page 161
4.2 Experimental Results......Page 162
References......Page 165
1 Introduction and Motivation......Page 167
2.1 An Introductory Example......Page 168
2.2 Definitions of Games and Equilibria......Page 170
2.3 State of the Art on Computing Equilibria......Page 171
3.1 Ingredients of the Encoding......Page 172
3.2 Encoding the Maximality Constraints......Page 173
3.3 Other Encodings......Page 174
4.1 Interval Propagation Techniques......Page 175
4.2 Reducing Variable Redundancy......Page 176
5.2 Experimental Conclusions......Page 178
6 Conclusion and Perspectives......Page 179
References......Page 180
1 Introduction......Page 182
2 The Covering Test Problem......Page 183
3.1 A Naive Matrix Model......Page 185
3.2 An Alternative Matrix Model......Page 186
3.4 Symmetry......Page 187
3.5 A Model for Local Search......Page 189
3.6 Summary of the Models......Page 190
5 Experiments......Page 191
References......Page 194
1 Introduction......Page 197
2.1 Motivation......Page 198
2.2 Forward Auctions: The Set Packing Problem......Page 199
3 Super Solutions and Combinatorial Auctions......Page 200
4 Experimental Results......Page 201
4.1 Constraint Satisfaction......Page 202
4.2 Constraint Optimization......Page 204
5 Extensions to Super Solutions......Page 207
6 Conclusion......Page 209
References......Page 210
1 Introduction......Page 211
2 Non-preemptive Single-Resource Constraint Problems......Page 212
3 Earliest Completion Times of Sets of Activities......Page 213
5 Propagation Rules......Page 216
6 Implementation and Complexity......Page 219
7 First Experiments......Page 222
References......Page 224
Back matter......Page 226