Data Mining and Constraint Programming - Foundations of a Cross-Disciplinary Approach

In industry, society, and science, advanced software is used for planning, scheduling, and allocating resources in order to improve the quality of service, reduce costs, or optimize resource consumption. Examples include power companies generating and distributing electricity, hospitals planning their surgeries, and public transportation companies scheduling their time-tables. This type of problem is often referred to as constraint satisfaction and combinatorial optimization problems. Despite the availability of effective and scalable solvers that are applicable to a wide range of applications, current approaches to this problem are still unsatisfactory. The reason is that in all these applications it is very hard to acquire the constraints and criteria (that is, the model) needed to specify the problem, and, even if one has succeeded in capturing the model at one point, it is likely that it needs to be to changed over time to reflect changes in the environment. Therefore, there is an urgent need for optimizing and revising a model over time based on data that should be continuously gathered about the performance of the solutions and the environment they are used in. Exploiting gathered data to modify the model is difficult and labour intensive with state-of-the-art solvers, as these solvers do not support data mining (DM) and machine learning (ML). However, existing frameworks for constraint satisfaction and combinatorial optimization problems do not support ML/DM techniques. In current ICT technology, DM and ML have almost always been studied independently from solving technology such as constraint programming (CP). On the other hand, a growing number of studies indicate that significant benefits can be obtained by connecting these two fields. This led us to believe – almost five years ago – that it was the right time to develop the foundations of an integrated and cross-disciplinary approach to these two fields. A successful integration of CP and DM has the potential to lead to a new ICT paradigm with far-reaching implications that would change the face of DM/ML as well as CP technology. It would not only allow one to use DM techniques in CP to identify and update constraints and optimization criteria, but also to employ such constraints and criteria in DM and ML in order to discover models compatible with such prior knowledge. This book reports on the key results obtained on this research topic within the European FP7 FET Open project no. 284715 on “Inductive Constraint Programming” and a number of associated workshops and Dagstuhl seminars