Recent Advances in Constraints

Constraint programming is a very successful ?fth-generation software techn- ogy with a wide range of applications. It has attracted a large community of researchers that is particularly strong in Europe. In particular, constraint programming is the focus of the Working Group on Constraints of the European Research Consortium for Informatics and Mat- matics (ERCIM) as well as a major interest of the European Network on C- putational Logic (CoLogNET). These groups jointly sponsored a workshop on Constraint Satisfaction and Constraint Logic Programming (CSCLP 2004) held June23 25attheEcolePolytechniqueF ed eraledeLausanne(EPFL)inSwitz- land. It was hosted by the Arti?cial Intelligence Laboratory of the EPFL, which is also a member of both groups. Thisbookpresentsacollectionofpapersthatareeitherrevisedandextended versions of papers accepted at the workshop, or were submitted in response to theopencallforpapersthatfollowed.The15papersinthisvolumewereselected from 30 submissions by rigorous peer review. The editors would like to take the opportunity to thank all authors and reviewers for the hard work they contributed to producing this volume. We also thank ERCIM and CoLogNET for their support of the workshop and the ?eld of constraint programming in general. We hope the reader will ?nd this volume helpful for advancing their understanding of issues in constraint programming. December 2004 Boi Faltings Adrian Petcu Francois Fages Francesca Rossi Organization This workshopwas jointly organized as the 9th Meeting of the ERCIM Working GrouponConstraints,coordinatedbyFrancois Fages,andthe2ndAnnualWo- shop of the CoLogNET area on Constraint Logic Programming, coordinated by Francesca Rossi. OrganizingInstitutes TheorganizationwashandledbytheEPFL,INRIAandtheUniversityofPadua.

Includes supplementary material: sn.pub/extras

Klappentext

TheorganizationwashandledbytheEPFL,INRIAandtheUniversityofPadua.

Inhalt
Constraint Propagation.- GCC-Like Restrictions on the Same Constraint.- A Note on Bilattices and Open Constraint Programming.- Pruning by Equally Constrained Variables.- Search.- Trying Again to Fail-First.- Characterization of a New Restart Strategy for Randomized Backtrack Search.- Dynamic Distributed BackJumping.- A Value Ordering Heuristic for Local Search in Distributed Resource Allocation.- Automatically Exploiting Symmetries in Constraint Programming.- New Structural Decomposition Techniques for Constraint Satisfaction Problems.- Applications.- Algorithms for the Maximum Hamming Distance Problem.- A System Prototype for Solving Multi-granularity Temporal CSP.- Computing Equilibria Using Interval Constraints.- Constraint-Based Approaches to the Covering Test Problem.- Super Solutions for Combinatorial Auctions.- Better Propagation for Non-preemptive Single-Resource Constraint Problems.