Introduction to the Special Issue on Local Search Techniques in Constraint Satisfaction

Constraint satisfaction plays an important role in theoretical and applied computer science. Constraint satisfaction problems (CSPs) are of particular interest to the constraint programming research community and for many real world applications. Along with pure systematic techniques for solving CSPs, stochastic local search (SLS) and hybrid techniques have proved to be very effective on some classes of problems. One central goal of research in SLS for constraint satisfaction is the design and implementation of efficient algorithms for use in stand-alone solvers or in conjunction with systematic techniques. As a result, there is a need to develop high-level SLS strategies that will lead to further progress towards the maturation of efficient and robust solvers for constraint satisfaction. The design and analysis of SLS algorithms for constraint satisfaction involves a wide range of issues related to algorithms, programming, statistics, probability and empirical analysis. The design of SLS techniques for CSP is also a typical system engineering process, as it involves modeling, design, analysis and implementation activities. Moreover, empirical analysis is crucial for the assessment of performance results and it has to comply with the scientific approach. This special issue of Constraints offers a representative selection of the current state-of-the-art in local search techniques for constraint satisfaction.