Abstract
Constraint Programming is a general framework used to model and 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 thenon-expert user in the modeling task. Nevertheless, in these systems the user is only asked to answervery 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 the constraints.In this thesis, we show that using the structure of the problem under consideration may improvethe acquisition process a lot. To this aim, we propose several techniques.Firstly, we introduce the concept of generalization 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.