La plupart des sc\'narios multimédia interactifs sont bas\'{e}s sur des sp\'cifications informelles, il n'est donc pas possible de v\'{e}rifier formellement des propri\'t\'{e}s de ces syst\'mes. Nous pr\'{e}conisons la n\'cessit\'{e} d'un mod\'le g\'{e}n\'ral et formel. Partitions interactives est un formalisme pour d\'{e}crire des sc\'narios multim\'{e}dia interactifs. Nous proposons une nouvelle s\'mantique pour les partitions interactives bas\'{e}e sur les structures d'\'v\'{e}nements temporisés. Avec une telle s\'mantique, nous pouvons sp\'{e}cifier des propri\'t\'{e}s pour le syst\'me, en particulier, des propri\'{e}t\'s sur les traces, qui sont difficiles \'{a} pr\'ciser avec la programmation par contraintes. Nous pr\'{e}sentons \'galement une s\'{e}mantique op\'rationnelle des partitions interactives bas\'{e}e sur le calcul non-d\'terministe, temporis\'{e}, concurrent, par contraintes (ntcc) et nous rapportons la s\'mantique operationelle \'{a} la semantique en structures d'\'v\'{e}nements temporisés. Avec la s\'mantique op\'{e}rationnelle, nous pouvons d\'crire formellement le comportement d'un scenario dont les dur\'{e}es des objets temporels peuvent \^{e}tre des intervalles d'entiers arbitraires. La s\'mantique op\'{e}rationnelle est obtenue \' partir de la s\'{e}mantique en structures d'\'v\'{e}nements temporisés de la partition interactive. Pour fournir une telle traduction, nous avons d'abord d\'fini la forme normale d'une structure d'\'{e}v\'nements temporisés, dans laquel les \'{e}v\'nements li\'{e}s avec une dur\'e z\'{e}ro sont regroup\'s en un seul. Nous avons \'{e}galement d\'fini la notion de structures d'\'{e}v\'nements temporisés r\'{e}partissables, de telle sorte que son graphe de contraintes peut \^{e}tre exp\'di\'{e} en se fondant uniquement sur la propagation locale. Nous croyons que la s\'mantique op\'{e}rationnelle bas\'e sur ntcc offre certains avantages par rapport \'{a} la s\'mantique des partitions interactives bas\'{e}e sur des r\'seaux de Petri; par exemple, les dur\'{e}es des objets temporels peuvent \^{e}tre des intervalles d'entiers arbitraires, tandis que dans la plupart des mod\'les de partitions interactives, les intervalles ne peut \^tre utilis\'{e}s que pour repr\'senter les relations telles que l'\'{e}galit\' et les inégalités. Nos mod\'{e}les ntcc de partitions interactives sont ex\'cut\'{e}s en utilisant Ntccrt, un interpr\'te temps r\'{e}el pour ntcc. Nos mod\'les peuvent \'{e}galement \^{e}tre v\'rifi\'{e}s automatiquement en utilisant ntccMC, un verificateur pour ntcc, de temps born\', bas\'{e}e sur les automates finis, que nous introduisons dans cette th\'se. En utilisant ntccMC, nous pouvons v\'{e}rifier des propri\'t\'{e}s de logique de temps lin\'aire avec des contrantes (CLTL). Dans cette th\'{e}se, nous introduisons deux extensions du formalisme de partitions interactives: (1) l'une pour g\'rer le traitement audio en utilisant le langage de programmation fran\c cais Faust et (2) l'autre pour traiter des condition et des branchements, permettant de sp\'{e}cifier des choix et des boucles. Pour la premi\'re extension, nous pr\'{e}sentons une s\'mantique bas\'{e}e sur les structures d'\'v\'{e}nements temporisés et des id\'es sur la fa\c con de d\'{e}finir une s\'mantique op\'{e}rationnelle. Pour la deuxi\'me extension, nous pr\'{e}sentons une mise en \oe uvre et la comparaison des r\'sultats du jitter relative moyenne d'une impl\'{e}mentation d'un arp\'ge base sur l'algorithme de Karplus-Strong par rapport aux impl\'{e}mentations existants \'crits dans Pure Data. Nous d\'{e}finissons aussi un format de sauvegarde XML pour les partitions interactives et pour la extension avec branchement conditionnel. Un format de sauvegarde est crucial pour assurer la persistance des partitions.

Le trafic aérien en Europe représente environ 30 000 vols quotidiens actuellement. Selon les prévisions de l’organisme Eurocontrol, ce trafic devrait croître de 70% d’ici l’année 2020 pour atteindre 50 000 vols quotidiens. L’espace aérien, découpé en zones géographiques appelées secteurs de contrôle, atteindra bientôt son niveau de saturation vis-à-vis des méthodes actuelles de planification et de contrôle. Afin d’augmenter la quantité de trafic que peut absorber le système, il est nécessaire de diminuer la charge de travail des contrôleurs aériens en les aidant dans leur tâche de séparation des avions. En se fondant sur les demandes de plans de vol des compagnies aériennes, nous proposons une méthode de planification des trajectoires en 4D permettant de présenter au contrôleur un trafic dont la plupart des conflits auront été évités en avance. Cette planification s’établit en deux étapes successives, ayant chacune un unique degré de liberté : une allocation de niveaux de vol permettant la résolution des conflits en croisière puis une allocation d’heures de décollage permettant de résoudre les conflits restants. Nous présentons des modèles pour ces deux problèmes d’optimisation fortement combinatoires, que nous résolvons en utilisant la programmation par contraintes ou les algorithmes évolutionnaires, ainsi que des techniques permettant de prendre en compte des incertitudes sur les heures de décollage ou le suivi de trajectoire. Les simulations conduites sur l’espace aérien français mènent à des situations où tous les conflits sont évités, avec des retards alloués de l’ordre d’une minute en moyenne (80 à90 minutes pour le vol le plus retardé) et un écart par rapport à l’altitude optimale limité à un niveau de vol pour la quasi totalité des vols. La prise en compte d’incertitudes de manière statique dégrade fortement ces solutions peu robustes, mais nous proposons un modèle dynamique utilisant une fenêtre glissante susceptible de prendre en compte des incertitudes de quelques minutes avec un impact réduit sur le coût de l’allocation. / Air traffic in Europe represents about 30,000 flights each day and forecasts from Eurocontrol predict a growth of 70% by 2020 (50,000 flights per day). The airspace, made up of numerous control sectors, will soon be saturated given the current planification and control methods. In order to make the system able to cope with the predicted traffic growth, the air traffic controllers workload has to be reduced by automated systems that help them handle the aircraft separation task. Based on the traffic demand by airlines, this study proposes a new planning method for 4D trajectories that provides conflict-free traffic to the controller. This planning method consists of two successive steps, each handling a unique flight parameter : a flight level allocation phase followed by a ground holding scheme. We present constraint programming models and an evolutionary algorithm to solve these large scale combinatorial optimization problems, as well as techniques for improving the robustness of the model by handling uncertainties of takeoff times and trajectory prediction. Simulations carried out over the French airspace successfully solved all conflicts, with a mean of one minute allocated delay (80 to 90 minutes for the most delayed flight) and a discrepancy from optimal altitude of one flight level for most of the flights. Handling uncertainties with a static method leads to a dramatic increase in the cost of the previous non-robust solutions. However, we propose a dynamic model to deal with this matter, based on a sliding time horizon, which is likely to be able to cope with a few minutes of uncertainty with reasonable impact on the cost of the solutions.

La programmation par contraintes intègre des algorithmes de résolution génériques dans des langages de modélisation déclaratifs basés sur les contraintes : ces langages permettent de décrire des problèmes combinatoires sous la forme d’un ensemble de variables devant prendre leurs valeurs dans des domaines en satisfaisant des contraintes. Nous introduisons dans cette thèse un algorithme de résolution générique paramétré par : — une stratégie d’exploration de l’espace de recherche, à choisir parmi, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, et backtracking with tree decomposition ; — une heuristique de choix de variables, à choisir parmi, min-domain/ddeg et min-domain/wdeg ; — une technique de propagation de contraintes, à choisir parmi, forward checking et maintaining arc consistency. Ainsi, cet algorithme générique s’instancie en vingt-quatre configurations différentes ; certaines correspondant à des algorithmes connus, d’autres étant nouvelles. Ces vingt- quatre configurations ont été comparées expérimentalement sur un benchmark de plus de mille instances, chaque configuration étant exécutée plusieurs fois sur chaque instance pour tenir compte du non déterminisme des exécutions. Des tests statistiques sont utilisés pour comparer les performances. Cette évaluation expérimentale a permis de mieux comprendre la complémentarité des différents mécanismes de résolution, avec une attention particulière portée sur la capacité à tirer parti de la structure des instances pour accélérer la résolution. Nous identifions notamment treize configurations complémentaires telles que chaque instance de notre benchmark est bien résolue par au moins une des treize configurations. Une deuxième contribution de la thèse est d’introduire un sélecteur capable de choisir automatiquement la meilleure configuration de notre algorithme générique pour chaque nouvelle instance à résoudre : nous décrivons chaque instance par un ensemble de descripteurs et nous utilisons des techniques d’apprentissage automatique pour construire un modèle de choix de configuration à partir de ces descripteurs. Sachant que l’apprentissage est généralement plus difficile quand il y a beaucoup de configurations, nous exprimons le problème du choix du sous-ensemble de configurations pouvant être sélectionnées comme un problème de couverture d’ensemble et nous comparons deux critères de choix : le premier vise à maximiser le nombre d’instances résolues par au moins une configuration et le second vise à maximiser le nombre d’instances pour lesquelles il y a une bonne configuration disponible. Nous montrons expérimentalement que la seconde stratégie obtient généralement de meilleurs résultats, et que le sélecteur obtient de meilleures performances que chacune de nos vingt-quatre configurations initiales. / Constraint programming integrates generic solving algorithms within declarative languages based on constraints : these languages allow us to describe combinatorial problems as a set of variables which have to take their values in domains while satisfying constraints. Numerous real-life problems can be modelled in such a way, as for instance, planification problems, scheduling problems, . . . These problems are NP-complete in the general case of finite domains. We introduce in this work a generic solving algorithm parameterized by : — a strategy for exploring the search space, to be chosen from the following six, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, and backtracking with tree decomposition ; — a variable ordering heuristic, to be chosen from the following two, min-domain/ddeg and min-domain/wdeg ; — a constraint propagation technique, to be chosen from the following two, forward checking and maintaining arc consistency. Thus, this algorithm leads to 24 different configurations ; some corresponding to already known algorithms, others being new. These 24 configurations have been com- pared experimentally on a benchmark of more than a thousand instances, each configuration being executed several times to take into account the non-determinism of the executions, and a statistical test has been used to compare performances. This experimental evaluation allowed us to better understand the complementarity of the different solving mechanisms, with a focus on the ability to exploit the structure of the instances to speed up the solving process. We identify 13 complementary configurations such that every instance of our benchmark is well solved by at least one of the 13 configurations. A second contribution of this work is to introduce a selector able to choose automatically the best configuration of our generic solver for each new instance to be solved : we describe each instance by a set of features and we use machine learning techniques to build a model to choose a configuration based on these features. Knowing that the learning process is generally harder when there are many configurations to choose from, we state the problem of choosing a subset of configurations that can be picked as a set covering problem and we compare two criterion : the first one aims to maximize the number of instances solved by at least one configuration and the second one aims to maximize the number of instances for which there is a good configuration available. We show experimentally that the second strategy obtains generally better results and that the selector obtains better performances than each of the 24 initial configurations.

Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudre. / The objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance.

Les ERP (Enterprise Resource Planning) sont incontournables dans les systèmes d'information des sociétés industrielles: ils jouent un rôle crucial pour automatiser et suivre leurs processus afin d'améliorer leur compétitivité. Un ERP est un logiciel générique qui est utilisé par plusieurs sociétés industrielles ayant des besoins et des processus différents. C'est pourquoi de nombreux paramètres permettent d'adapter le fonctionnement du système aux besoins d'une société. Le déploiement d'un ERP, qui vise à paramétrer le système en fonction des besoins collectés, est donc une tâche complexe qui requiert une profonde expertise du système mais aussi du métier de l'entreprise industrielle. Infologic est une société qui développe et installe son propre ERP appelé Copilote. La difficulté liée au déploiement de Copilote dans une société industrielle est un réel frein pour la croissance d'Infologic et réduire la complexité du paramétrage de Copilote est un enjeu vital pour Infologic. C'est pourquoi nous avons étudié le processus de déploiement de Copilote et particulièrement la phase de paramétrage du système. Nous proposons une approche visant à extraire, depuis l'ensemble des paramétrages existants, un catalogue de paramétrages correspondant à des besoins fonctionnels précédemment rencontrés afin de les réutiliser lors des prochains déploiements de Copilote. Nous proposons d’utiliser la programmation par contraintes pour cela, afin de pouvoir facilement personnaliser les solutions calculées en ajoutant des contraintes et des critères d’optimisation variés. Nous introduisons de nouveaux modèles à base de contraintes pour résoudre des problèmes de clustering conceptuel, ainsi qu'une contrainte globale pour le problème de couverture exacte avec plusieurs algorithmes de propagation. Nous montrons qu'elle permet de modéliser facilement des problèmes de clustering conceptuel, et de les résoudre plus efficacement que les approches déclaratives de l’état de l’art. / Enterprise Resource Planning (ERP) systems are essential for industrial companies to automatize and monitor their business processes in order to boost their competitiveness. ERP systems are generic software designed to serve a large variety of companies with different business processes. Therefore, they have many configuration options to support various business processes used in different companies. The implementation process of an ERP system consists in assigning values to ERP parameters according to the company requirements: It determines the exact operations and processes supported by the system in the specific company. Infologic is a French company that develops and integrates their own ERP system called Copilote. It has thousands of parameters that are used to adapt it as precisely as possible to customer requirements. However, this flexibility makes the implementation of Copilote a time consuming task that requires a deep knowledge of its functionalities and parameters. Reducing the complexity of the implementation of Copilote is a critical issue for Infologic who needs to integrate efficiently new system integrators to meet the demand of new customers. In this thesis, we study the implementation process of Copilote in order to understand the main issues encountered by Infologic. We propose a new approach for extracting a catalog of configuration parts from existing configurations of Copilote, and each configuration part is associated with the business requirement it fulfills in order to reuse it for next implementations of Copilote. To this aim, we propose to use constraint programming (CP) to easily integrate feedbacks of experts by means of new constraints or criteria. We introduce new CP models to solve conceptual clustering problems and a new global constraint for the exact cover problem with several propagation algorithms. We show it allows to model easily conceptual clustering problems and to solve it more efficiently thant existing delcarative approaches.

La matérialisation de vues est une technique très utilisée dans les systèmes de gestion bases de données ainsi que dans les entrepôts de données pour améliorer les performances des requêtes. Elle permet de réduire de manière considérable le temps de réponse des requêtes en pré-calculant des requêtes coûteuses et en stockant leurs résultats. De ce fait, l'exécution de certaines requêtes nécessite seulement un accès aux vues matérialisées au lieu des données sources. En contrepartie, la matérialisation entraîne un surcoût de maintenance des vues. En effet, les vues matérialisées doivent être mises à jour lorsque les données sources changent afin de conserver la cohérence et l'intégrité des données. De plus, chaque vue matérialisée nécessite également un espace de stockage supplémentaire qui doit être pris en compte au moment de la sélection. Le problème de choisir quelles sont les vues à matérialiser de manière à réduire les coûts de traitement des requêtes étant donné certaines contraintes tel que l'espace de stockage et le coût de maintenance, est connu dans la littérature sous le nom du problème de la sélection de vues. Trouver la solution optimale satisfaisant toutes les contraintes est un problème NP-complet. Dans un contexte distribué constitué d'un ensemble de noeuds ayant des contraintes de ressources différentes (CPU, IO, capacité de l'espace de stockage, bande passante réseau, etc.), le problème de la sélection des vues est celui de choisir un ensemble de vues à matérialiser ainsi que les noeuds du réseau sur lesquels celles-ci doivent être matérialisées de manière à optimiser les coût de maintenance et de traitement des requêtes.Notre étude traite le problème de la sélection de vues dans un environnement centralisé ainsi que dans un contexte distribué. Notre objectif est de fournir une approche efficace dans ces contextes. Ainsi, nous proposons une solution basée sur la programmation par contraintes, connue pour être efficace dans la résolution des problèmes NP-complets et une méthode puissante pour la modélisation et la résolution des problèmes d'optimisation combinatoire. L'originalité de notre approche est qu'elle permet une séparation claire entre la formulation et la résolution du problème. A cet effet, le problème de la sélection de vues est modélisé comme un problème de satisfaction de contraintes de manière simple et déclarative. Puis, sa résolution est effectuée automatiquement par le solveur de contraintes. De plus, notre approche est flexible et extensible, en ce sens que nous pouvons facilement modéliser et gérer de nouvelles contraintes et mettre au point des heuristiques pour un objectif d'optimisation.Les principales contributions de cette thèse sont les suivantes. Tout d'abord, nous définissons un cadre qui permet d'avoir une meilleure compréhension des problèmes que nous abordons dans cette thèse. Nous analysons également l'état de l'art des méthodes de sélection des vues à matérialiser en en identifiant leurs points forts ainsi que leurs limites. Ensuite, nous proposons une solution utilisant la programmation par contraintes pour résoudre le problème de la sélection de vues dans un contexte centralisé. Nos résultats expérimentaux montrent notre approche fournit de bonnes performances. Elle permet en effet d'avoir le meilleur compromis entre le temps de calcul nécessaire pour la sélection des vues à matérialiser et le gain de temps de traitement des requêtes à réaliser en matérialisant ces vues. Enfin, nous étendons notre approche pour résoudre le problème de la sélection de vues à matérialiser lorsque celui-ci est étudié sous contraintes de ressources multiples dans un contexte distribué. A l'aide d'une évaluation de performances extensive, nous montrons que notre approche fournit des résultats de qualité et fiable. / View selection is important in many data-intensive systems e.g., commercial database and data warehousing systems to improve query performance. View selection can be defined as the process of selecting a set of views to be materialized in order to optimize query evaluation. To support this process, different related issues have to be considered. Whenever a data source is changed, the materialized views built on it have to be maintained in order to compute up-to-date query results. Besides the view maintenance issue, each materialized view also requires additional storage space which must be taken into account when deciding which and how many views to materialize.The problem of choosing which views to materialize that speed up incoming queries constrained by an additional storage overhead and/or maintenance costs, is known as the view selection problem. This is one of the most challenging problems in data warehousing and it is known to be a NP-complete problem. In a distributed environment, the view selection problem becomes more challenging. Indeed, it includes another issue which is to decide on which computer nodes the selected views should be materialized. The view selection problem in a distributed context is now additionally constrained by storage space capacities per computer node, maximum global maintenance costs and the communications cost between the computer nodes of the network.In this work, we deal with the view selection problem in a centralized context as well as in a distributed setting. Our goal is to provide a novel and efficient approach in these contexts. For this purpose, we designed a solution using constraint programming which is known to be efficient for the resolution of NP-complete problems and a powerful method for modeling and solving combinatorial optimization problems. The originality of our approach is that it provides a clear separation between formulation and resolution of the problem. Indeed, the view selection problem is modeled as a constraint satisfaction problem in an easy and declarative way. Then, its resolution is performed automatically by the constraint solver. Furthermore, our approach is flexible and extensible, in that it can easily model and handle new constraints and new heuristic search strategies for optimization purpose. The main contributions of this thesis are as follows. First, we define a framework that enables to have a better understanding of the problems we address in this thesis. We also analyze the state of the art in materialized view selection to review the existing methods by identifying respective potentials and limits. We then design a solution using constraint programming to address the view selection problem in a centralized context. Our performance experimentation results show that our approach has the ability to provide the best balance between the computing time to be required for finding the materialized views and the gain to be realized in query processing by materializing these views. Our approach will also guarantee to pick the optimal set of materialized views where no time limit is imposed. Finally, we extend our approach to provide a solution to the view selection problem when the latter is studied under multiple resource constraints in a distributed context. Based on our extensive performance evaluation, we show that our approach outperforms the genetic algorithm that has been designed for a distributed setting.

La Programmation par contraintes est un cadre général utilisé pour modéliser et résoudre des problèmes combinatoires complexes. Cependant, la modélisation d'un problème sous forme d’un réseau de contraintes nécessite une bonne expertise dans le domaine. Ce niveau d'expertise est un obstacle majeur pour une large diffusion de la programmation de contraintes. Pour remédier à ce problème, plusieurs systèmes d'acquisition de contraintes ont été proposés pour aider l'utilisateur dans la tâche de modélisation. Dans ces systèmes, l'utilisateur ne répond qu'à des questions très simples. L'inconvénient est que lorsqu'aucune connaissance de base n’est fournie, l'utilisateur peut avoir besoin de répondre à un grand nombre de questions pour apprendre toutes les contraintes. Dans cette thèse, nous montrons que l'utilisation de la structure du problème peut améliorer considérablement le processus d'acquisition. Pour ce faire, nous proposons plusieurs techniques. Tout d'abord, nous introduisons le concept de requête de généralisation basée sur une agrégation de variables sous forme detypes. Deuxièmement, pour faire face aux requêtes de généralisation, nous proposons un algorithme de généralisation de contraintes, nommé GENACQ, ainsi que plusieurs stratégies. Troisièmement, pour rendre la construction de requêtes de généralisation totalement indépendante de l'utilisateur, nous proposons l'algorithme MINE&ASK, qui est en mesure d'apprendre la structure au cours du processus d'acquisition de contraintes, et d'utiliser la structure apprise pour générer des requêtes de généralisation. Quatrièmement, pour aller vers un concept générique de requête, nous introduisons la requête de recommandation basée sur la prédiction de liens dans le graphe de contraintes apprises jusqu’à présent. Cinquièmement, nous proposons un algorithme de recommandation de contraintes, ppelé PREDICT&ASK, qui demande à l’utilisateur de classifier des requêtes de recommandation chaque fois que la structure du graphe courant a été modifiée. Enfin, nous intégrons toutes ces nouvelles techniques dans l’algorithme QUACQ, menant à trois nouvelles versions, à savoir G-QUACQ, M- QUACQ, et P-QUACQ. Pour évaluer toutes ces techniques, nous avons fait des expérimentations sur plusieurs jeux de données. Les résultats montrent que les versions étendues améliorent considérablement le QUACQ de base. / 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.

Disposer de données dans le but de valider ou tester une approche ou un concept est d'une importance primordiale dans beaucoup de domaines différents. Malheureusement, ces données ne sont pas toujours disponibles, sont coûteuses à obtenir, ou bien ne répondent pas à certaines exigences de qualité ce qui les rend inutiles dans certains cas de figure.Un générateur automatique de données est un bon moyen pour obtenir facilement et rapidement des données valides, de différentes tailles, pertinentes et diversifiées. Dans cette thèse, nous proposons une nouvelle approche complète, dirigée par les modèles et basée sur la programmation par contraintes pour la génération de données. / Owning data is useful in many different fields. Data can be used to test and to validate approaches, algorithms and concepts. Unfortunately, data is rarely available, is cost to obtain, or is not adapted to most of cases due to a lack of quality.An automated data generator is a good way to generate quickly and easily data that are valid, in different sizes, likelihood and diverse.In this thesis, we propose a novel and complete model driven approach, based on constraint programming for automated data generation.

Em um mercado global, tem sido observada a tendência para a dispersão geográfica das fabricas. Esta dispersão e motivada pela oportunidade de explorar as vantagens locais, sob diferentes pontos de vista. Essa estrutura também permite a interação mais intensa entre plantas de diferentes empresas produtivas. Neste sentido, o conceito de Empresa Virtual (EV) e fundamental para explorar novas estratégias de negócios, tais como foco nas competências essenciais, orientação máxima para o cliente e produção distribuída. No entanto, nesta nova estrutura produtiva, há novos requisitos para o planejamento e para o estabelecimento da data de entrega dos pedidos. Um sistema de Planejamento e Controle da Produção (PCP) convencional utiliza uma arquitetura hierárquica, o que não atende o requisito de autonomia das empresas parceiras. Para atender a essas novas exigências, este trabalho apresenta uma arquitetura de sistemas de planejamento e controle da produção no contexto de EV. Na proposta são utilizados os conceitos de janelas de tempo em conjunto com propagação de restrições para atender os requisitos de prazo de entrega de produtos. Estes dois conceitos tem sido amplamente utilizados na literatura relacionada a sistemas de planejamento convencionais, no entanto, não no contexto de EV. Nesta abordagem, as janelas de tempo delimitam o intervalo de alocação das tarefas nos sistemas de produção envolvidos, enquanto as restrição de capacidade identificam janelas de tempo factíveis considerando a importância da data de vencimento do pedido. E apresentado um exemplo da utilização da arquitetura e um exemplo de implementação. Este trabalho engloba EVs com empresas parceiras de diversos tipos de produção (produção em lotes e produção discreta). E utilizado o Production Flow Schema (PFS) para modelagem dos processos produtivos segundo uma abordagem hierárquica, com base em sucessivos renamentos para construir o modelo de forma progressiva e estruturada onde as propriedades do modelo ficam asseguradas por construção. Este refinamento gera sub-grafos em Rede de Petri, que são utilizados para a analise e o controle do processo produtivo. / In a global market, the trend for geographical dispersion of manufacturing plants has been observed. This dispersion is motivated by the opportunity to exploit local advantages under dierent viewpoints. This structure also allows for more intense interaction between plants of dierent productive enterprises. In this sense, the concept of Virtual Enterprise (VE) is fundamental to explore new business strategies such asfocus on core competencies,maximal customer orientationanddistributed production. However, in this new productive structure, there are new requirements for planning and for establishing the delivery date of the orders. A conventional Production Planning and Control system (PPC) uses a hierarchical architecture, which does not meet the requirement of autonomy of the partners companies. To address these new requirements, this work introduces a Production Planning and Control System Architecture in EV context. In the proposal are used the concepts oftime windowsandconstraint propagationto meet the deadline requirements of product delivery. These two concepts have been widely used in the literature relating to conventional planning systems, however, not in the EV context. In this approach, thetime windowsdelimit the allocation range of tasks in production systems involved, while the capacity constraint identify the feasible time window considering the importance of the ordes due date. An example of using the architecture and an implementation is presented. This work includes EVs with partner companies of various types of production (production batch and discrete manufacturing). Production Flow Schema (PFS) is used for modeling the processes according to a hierarchical approach based on successive renements to construct progressive and structured model where the properties of model are ensured by construction. This renement generates sub-graphs in Petri Net, which are used for the analysis and control of the production process.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d’origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d’ordonnancement cumulatif. Un problème d’ordonnancement consiste à déterminer les dates de débuts et de fins d’un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l’on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l’on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l’aide d’algorithmes dédiés et de métaheuristiques. Par exemple, l’utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d’ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l’idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d’accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l’arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d’un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d’ordonnancement. / Constraint programming is an approach often used to solve combinatorial problems in different application areas. In this thesis we focus on the cumulative scheduling problems. A scheduling problem is to determine the starting dates of a set of tasks while respecting capacity and precedence constraints. Capacity constraints affect both conventional cumulative constraints where the sum of the heights of tasks intersecting a given time point is limited, and colored cumulative constraints where the number of distinct colors assigned to the tasks intersecting a given time point is limited. A newly identified challenge for constraint programming is to deal with large problems, usually solved by dedicated algorithms and metaheuristics. For example, the increasing use of virtualized datacenters leads to multi dimensional placement problems of thousand of jobs. Scalability is achieved by using a synchronized sweep algorithm over the different cumulative and precedence constraints that allows to speed up convergence to the fix point. In addition, from these filtering algorithms we derive greedy procedures that can be called at each node of the search tree to find a solution more quickly. This approach allows to deal with scheduling problems involving more than one million jobs and 64 cumulative resources. These algorithms have been implemented within Choco and SICStussolvers and evaluated on a variety of placement and scheduling problems.