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.

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.

Nous nous intéressons au problème du dimensionnement et du placement optimal de locaux sur une surface donnée (on trouve aussi allocation spatiale), de type logements familiaux, bureaux ou équipements collectifs... Nous présentons une nouvelle approche de logiciel de CAO en architecture qui part de l'expression du besoin fonctionnel en termes de contraintes sur les locaux. La grande originalité de ce travail est de proposer un modèle de placement a trois niveaux : fonctionnel, topologique et numérique. Dans une seconde étape, le logiciel ARCHiPLAN que nous avons développé, énumère toutes les solutions topologiquement différentes, sans présumer pour autant de dimensions finales précises. Ces solutions correspondent à l'étape d'esquisses qu'effectue un architecte en phase de conception préliminaire a partir du cahier des charges fonctionnel (programme). L'architecte peut ensuite « naviguer » dans cet espace de solutions topologiques, en faible nombre, et en choisir certaines pour une étude plus poussée. Pour chaque solution topologique, la meilleure solution dimensionnelle est trouvée au regard de critères de coûts, de surfaces utiles, de trame ou autres. Cette approche, qui combine la programmation orientée objet et les techniques de programmation par contraintes, a l'avantage d'éviter le problème récurrent de l'explosion combinatoire grâce a ce modèle a trois niveaux, tout en se rapprochant de la pratique du concepteur du domaine par une méthode fonctionnelle et progressive. Le logiciel ARCHiPLAN a prouve sa robustesse, sa pertinence et sa souplesse en conception ainsi que sa rapidite sur de nombreux exemples.

Les systèmes de contraintes de distance euclidienne apparaissent dans de nombreux domaines d'applications, comme en robotique, en biochimie<br />moléculaire ou en CAO. Les techniques issues de la programmation par contraintes permettent de résoudre ces problèmes en combinant une technique de bissection avec des méthodes de réduction des domaines (consistances locales ou partielles). Or, ces consistances sont des méthodes systématiques qui ne prennent pas en compte les propriétés spécifiques des contraintes.<br /><br />Nous présentons dans cette thèse deux approches pour la conception d'une contrainte globale pour la résolution de systèmes de contraintes de distance. La première approche est basée sur l'inférence de contraintes<br />redondantes directement issues de propriétés géométriques du système.<br />La deuxième approche est basée sur l'introduction d'un algorithme de filtrage global dédié aux systèmes d'équations de distance.<br />Ces travaux ont débouché sur la conception d'une<br />technique de décomposition de domaines qui exploite la structure particulière des contraintes de distance. Enfin, nous présentons une généralisation de cette heuristique de recherche à des contraintes numériques quelconques.

Les systèmes embarqués sont des dispositifs électroniques et informatiques autonomes, dédiés à une tâche bien précise. Leur utilisation s'est désormais démocratisée à de nombreux domaines d'applications et en particulier au multimédia. Ce type d'application est caractérisé par un besoin important en puissance de calcul et en échange de données. Les architectures matérielles au cœur de ces systèmes sont généralement dotées d'accélérateurs chargés de l'exécution des noyaux de calcul intensif. Les architectures reconfigurables à gros grain (CGRA) sont particulièrement adaptées à l'accélération d'applications multimédia car elles répondent au mieux aux contraintes de performance, d'efficacité énergétique, de flexibilité et de coût de conception. En effet, ce type d'architecture est un compromis entre les processeurs à usage général, les architectures dédiées et celles reconfigurables à grain fin. Cette thèse traite de certains aspects liés aux problématiques de conception et de compilation d'applications pour CGRA. Nos travaux s'inscrivent dans une démarche d'adéquation applications multimédia / CGRA / conception et compilation basées sur la programmation par contraintes (CP). Notre méthodologie nous a permis, grâce à la CP, de modéliser et de résoudre un ensemble de problèmes combinatoires complexes. Le premier modèle présenté a trait à la fusion d'unités fonctionnelles reconfigurables sous contraintes architecturales et technologiques. Les deux autres modèles abordent les problèmes de : placement, ordonnancement et routage des données pour le déploiement d'une application sur CGRA. Notre approche permet, dans la majorité des cas, de prouver l'optimalité de la solution obtenue.

Les processeurs à jeux d'instructions spécifiques (ASIP) sont des processeurs spécialisés qui combinent la flexibilité d'un processeur programmable avec la performance d'un processeur dédié. L'une des approches de conception de tels processeurs consiste à spécialiser un cœur de processeur existant en y ajoutant des instructions spécialisées, mises en œuvre dans un module matériel fortement couplé au chemin de données du processeur. C'est l'extension de jeu d'instructions. La conception d'un ASIP nécessite des méthodologies et des outils logiciels appropriés garantissant une maîtrise des contraintes de conception et de la complexité grandissante des applications. Dans ce contexte, cette thèse vise à proposer une méthodologie de génération automatique d'extensions de jeux d'instructions. Celle-ci consiste à tout d'abord identifier l'ensemble des instructions candidates qui satisfont les contraintes architecturales et technologiques, afin de garantir leurs mises en œuvre. Ensuite, les instructions candidates qui minimisent le temps d'exécution séquentielle de l'application sont sélectionnées. Les ressources matérielles de l'extension, telles que les registres et les multiplexeurs, sont optimisées. Enfin, la dernière étape génère la description matérielle et le modèle de simulation de l'extension. Le code applicatif est adapté pour tenir compte des nouvelles instructions. Cette thèse propose des techniques basées sur la programmation par contraintes pour résoudre les problèmes difficiles (voir intraitables) que sont l'identification d'instructions, la sélection d'instructions et l'allocation de registres.

La conception architecturale de systèmes mécaniques et énergétiques permet d'étudier la faisabilité de concepts préalablement choisis pendant la phase de recherche de concepts. Elle fait partie de la phase de conception préliminaire et son achèvement vise à définir l'architecture globale qui sera étudiée pendant la phase de conception détaillée d'un produit. Les principales caractéristiques d'un produit (dimensions, choix de composants, de formes, de topologies ou de matériaux) sont alors fondamentales à ce stade de la conception. La conception architecturale nécessite aussi la prise en compte des comportements physiques et des interactions du produit, de ses composants et des milieux extérieurs, de critères économiques, environnementaux, etc. suivant les exigences du cahier des charges fonctionnel. Le concepteur définit un modèle mathématique exprimant cette connaissance liée au produit. Ce modèle peut être traité à l'aide d'un solveur de Problèmes de Satisfaction de Contraintes numériques (CSP). Ce type de solveur traite de manière générique des problèmes formulés à l'aide de contraintes, de variables et de domaines. Nous proposons de nouveaux algorithmes et de nouvelles heuristiques qui prennent en compte des besoins spécifiques au concepteur en conception préliminaire, comme : la classification des variables, les précisions relatives aux valeurs de certaines variables, les contraintes par morceaux. Les études de faisabilité de plusieurs systèmes mécaniques et énergétiques ont été réalisées avec succès. Les nouveaux algorithmes ont permis de diminuer significativement les temps de calculs, mais ils ont aussi permis d'améliorer la qualité des solutions calculées au regard des besoins du concepteur.

Ce document décrit de nouvelles modélisations et approches de résolution que nous appliquons à des problèmes de découpe et de conditionnement. Nous étudions dans un premier temps plusieurs techniques de décomposition alliées à différentes méta-heuristiques basées sur des stratégies d'oscillation. Nous étudions ensuite le concept de fonctions dual-réalisables qui permettent d'obtenir des évaluations par défaut polynomiales pour des problèmes de conditionnement. Finalement, nous proposons des modèles originaux pour des problèmes de placement de rectangles. Nous utilisons ces modèles dans des méthodes de programmation par contraintes.