"Learning and Using Structures for Constraint Acquisition" by Abderrazak Daoudi

Seminar by Abderrazak Daoudi, Teaching Assistant (ATER) at the Hubert Curien laboratory

Constraint Programming is a general framework used to model and to solve complex combinatorial problems. However, modeling a problem as a constraint network requires significant expertise in the field. Such level of expertise is a bottleneck to the broader uptake of the constraint technology. To alleviate this issue, several constraint acquisition systems have been proposed to assist the non-expert user in the modeling task. Nevertheless, in these systems the user is only asked to answer very basic questions. The drawback is that when no background knowledge is provided, the user may need to answer a large number of such questions to learn all theconstraints. In this talk, we show that using the structure of the problem under consideration may improve the acquisition process a lot. To thisaim, we propose several techniques. Firstly, we introduce the concept ofgeneralization query based on an aggregation of variables into types. Secondly, to deal with generalization queries, we propose a constraint generalization algorithm, named GENACQ, together with several strategies. Thirdly, to make the build of generalization queries totally independent of the user, we propose the algorithm MINE&ASK, which is able to learn the structure, during the constraint acquisition process, and to use the learned structure to generate generalization queries. Fourthly, toward a generic concept of query, we introduce the recommendation query based on the link prediction on the current constraint graph. Fifthly, we propose a constraint recommender algorithm, called PREDICT&ASK, that asks recommendation queries, each time the structure of the current graph has been modified. Finally, we incorporate all these new generic techniques into QUACQ algorithm leading to three boosted versions,   G-QUACQ, M-QUACQ, and P-QUACQ. To evaluate all these techniques, we have made experiments on several benchmarks. The results show that the extended versions improve drastically the basic QUACQ.