Au cours de la dernière décennie les technologies de cloud computing ont connu un essor considérable se traduisant par la montée en flèche de la consommation électrique des data center. L’ampleur du problème a motivé de nombreux travaux de recherche s’articulant autour de solutions de réduction statique ou dynamique de l’enveloppe globale de consommation électrique d’un data center. L’objectif de cette thèse est d’intégrer les sources d’énergie renouvelables dans les modèles d’optimisation dynamique d’énergie dans un data center. Pour cela nous utilisons la programmation par contraintes ainsi que des techniques d’apprentissage machine. Dans un premier temps, nous proposons une contrainte globale d’intersection de tâches tenant compte d’une ressource à coûts variables. Dans un second temps, nous proposons deux modèles d’apprentissage pour la prédiction de la charge de travail d’un data center et pour la génération de telles courbes. Enfin, nous formalisons le problème de planification énergiquement écologique (PPEE) et proposons un modèle global à base de PPC ainsi qu’une heuristique de recherche pour le résoudre efficacement. Le modèle proposé intègre les différents aspects inhérents au problème de planification dynamique dans un data center : machines physiques hétérogènes, types d’applications variés (i.e., applications interactives et applications par lots), opérations et coûts énergétiques de mise en route et d’extinction des machines physiques, interruption/reprise des applications par lots, consommation des ressources CPU et RAM des applications, migration des tâches et coûts énergétiques relatifs aux migrations, prédiction de la disponibilité d’énergie verte, consommation énergétique variable des machines physiques. / Over the last decade, cloud computing technologies have considerably grown, this translates into a surge in data center power consumption. The magnitude of the problem has motivated numerous research studies around static or dynamic solutions to reduce the overall energy consumption of a data center. The aim of this thesis is to integrate renewable energy sources into dynamic energy optimization models in a data center. For this we use constraint programming as well as machine learning techniques. First, we propose a global constraint for tasks intersection that takes into account a ressource with variable cost. Second, we propose two learning models for the prediction of the work load of a data center and for the generation of such curves. Finally, we formalize the green energy aware scheduling problem (GEASP) and propose a global model based on constraint programming as well as a search heuristic to solve it efficiently. The proposed model integrates the various aspects inherent to the dynamic planning problem in a data center : heterogeneous physical machines, various application types (i.e., ractive applications and batch applications), actions and energetic costs of turning ON/OFF physical machine, interrupting/resuming batch applications, CPU and RAM ressource consumption of applications, migration of tasks and energy costs related to the migrations, prediction of green energy availability, variable energy consumption of physical machines.

Cette thèse s’intéresse à la création automatique de résumés de vidéos. L’idée est de créer de manière adaptative un résumé vidéo qui prenne en compte des règles définies sur le contenu audiovisuel d’une part, et qui s’adapte aux préférences de l’utilisateur d’autre part. Nous proposons une nouvelle approche qui considère le problème de création automatique de résumés sous forme d’un problème de satisfaction de contraintes. La solution est basée sur la programmation par contraintes comme paradigme de programmation. Un expert commence par définir un ensemble de règles générales de production du résumé, règles liées au contenu multimédia de la vidéo d’entrée. Ces règles de production sont exprimées sous forme de contraintes à satisfaire. L’utilisateur final peut alors définir des contraintes supplémentaires (comme la durée souhaitée du résumé) ou fixer des paramètres de haut niveau des contraintes définies par l’expert. Cette approche a plusieurs avantages. Elle permet de séparer clairement les règles de production des résumés (modélisation du problème) de l’algorithme de génération de résumés (la résolution du problème par le solveur de contraintes). Le résumé peut donc être adapté sans qu’il soit nécessaire de revoir tout le processus de génération des résumés. Cette approche permet par exemple aux utilisateurs d’adapter le résumé à l’application cible et à leurs préférences en ajoutant une contrainte ou en modifiant une contrainte existante, ceci sans avoir à modifier l’algorithme de production des résumés. Nous avons proposé trois modèles de représentation des vidéos qui se distinguent par leur flexibilité et leur efficacité. Outre les originalités liées à chacun des trois modèles, une contribution supplémentaire de cette thèse est une étude comparative de leurs performances et de la qualité des résumés résultants en utilisant des mesures objectives et subjectives. Enfin, et dans le but d’évaluer la qualité des résumés générés automatiquement, l’approche proposée a été évaluée par des utilisateurs à grande échelle. Cette évaluation a impliqué plus de 60 personnes. Ces expériences ont porté sur le résumé de matchs de tennis. / This thesis focuses on the issue of automatic video summarization. The idea is to create an adaptive video summary that takes into account a set of rules defined on the audiovisual content on the one hand, and that adapts to the users preferences on the other hand. We propose a novel approach that considers the problem of automatic video summarization as a constraint satisfaction problem. The solution is based on constraint satisfaction programming (CSP) as programming paradigm. A set of general rules for summary production are inherently defined by an expert. These production rules are related to the multimedia content of the input video. The rules are expressed as constraints to be satisfied. The final user can then define additional constraints (such as the desired duration of the summary) or enter a set of high-level parameters involving to the constraints already defined by the expert. This approach has several advantages. This will clearly separate the summary production rules (the problem modeling) from the summary generation algorithm (the problem solving by the CSP solver). The summary can hence be adapted without reviewing the whole summary generation process. For instance, our approach enables users to adapt the summary to the target application and to their preferences by adding a constraint or modifying an existing one, without changing the summaries generation algorithm. We have proposed three models of video representation that are distinguished by their flexibility and their efficiency. Besides the originality related to each of the three proposed models, an additional contribution of this thesis is an extensive comparative study of their performance and the quality of the resulting summaries using objective and subjective measures. Finally, and in order to assess the quality of automatically generated summaries, the proposed approach was evaluated by a large-scale user evaluation. This evaluation involved more than 60 people. All these experiments have been performed within the challenging application of tennis match automatic summarization.

Dans le cadre du projet PAJERO, nous présentons dans cette thèse une parallélisation externe d'un solveur de Programmation Par Contraintes (PPC) basée sur des méthodes de parallélisation de la search et Portfolio. Cela, afin d'améliorer la performance de la résolution des problèmes de satisfaction et d'optimisation sous contraintes. La parallélisation de la search que nous proposons est adaptée pour une exécution en mode opportuniste et déterministe, suivant les besoins des clients. Le principe consiste à partitionner à la demande l'arbre de recherche unique généré par une seule stratégie de recherche en un ensemble de sous-arbres, pour ensuite affecter chaque sous-arbre à un coeur de calcul. Une stratégie de recherche est un algorithme qui choisit pour chaque noeud dans l'arbre de recherche la variable à assigner et choisi également l'ordonnancement de la recherche. En PPC, il existe plusieurs stratégies de recherche, certaines sont plus efficaces que d'autres, mais cela dépend généralement de la nature des problèmesde contraintes. Cependant la difficulté reste de choisir la bonne stratégie. Pour bénéficier de la variété des stratégies et de la disponibilité des ressources de calcul, un autre type de parallélisation est proposé, appelé Portfolio. La parallélisationPortfolio consiste à exécuter en parallèle N stratégies de recherche, ensuite la première stratégie qui trouve une solution met fin à toutes les autres. La nouveauté que nous proposons dans la parallélisation Portfolio consiste à adapterl'ordonnancement des N stratégies entre elles afin de privilégier la stratégie la plus prometteuse. Cela en lui donnant plus de coeurs que les autres. Pour ceci nous appliquons soit une fonction d'estimation pour chaque stratégie afin de sélectionner la stratégie qui a le plus petit arbre de recherche, soit un algorithme d'apprentissage qui permet de prédire quelle est la meilleure stratégie suivant le résultat d'un apprentissage effectué sur des instances déjà résolues. Afin d'ordonnancer plusieurs applications de PPC, nous proposons également un nouveau système d'allocation de ressources basé sur une stratégie d'ordonnancement combinée avec un modèle économique. Les applications de PPC sont résolues avec des solveurs parallèles dans une infrastructure cloud computing. L'originalité du system d'allocation est qu'il détermine automatiquement le nombre de ressources à affecter pour chaque application suivant la classe économique du client. Les performances obtenues avec nos méthodes de parallélisation sont illustrées par la résolution des problèmes de contraintes en portant le solveur Google OR-Tools au-dessus de notre framework parallèle Bobpp / In the context of the PAJERO project, we propose in this thesis an external parallelization of a Constraint Programming (CP) solver, using both search and Portfolio parallelizations, in order to solve constraint satisfaction and optimization problems. In our work the search parallelization is adapted for deterministic and non-deterministic executions, according to the needs of the user. The principle is to partition the unique search tree generated by one search strategy into a set of sub-trees, then assign each sub-tree to one computing core. A search strategy herein means an algorithm to decide which variable is selected to be assigned in each node of the search tree, and decide also the scheduling of the search. In CP, several search strategies exist and each one could be better than others for solving a specific problem. The difficulty lies in how to choose the best strategy. To benefit from the variety of strategies and the availability of computationalresources, another parallelization exists called the Portfolio parallelization. The principle of this Portfolio parallelization is to execute N search strategies in parallel. The first strategy which find a solution stops the others. The noveltyof our work in the context of the Portfolio is to adapt the schedule of the N strategies in order to favour the most promising strategy, which is a candidate to find a solution first, by giving it more cores than others. The promising strategyis selected using two methods. The first method is to use an estimation function which select the strategy with the smallest search tree. The second method is to use a learning algorithm which automatically determines the number of cores thatwill be allocated to each strategy according to the previous experiment. We have also proposed a new resource allocation system based on a scheduling strategy used with an economic model in order to execute several PPC applications. Thisapplications are solved using parallel solvers in the cloud computing infrastructure. The originality of this system is that the number of resources allocated to each PPC application is determined automatically according the economic classesof the users. The performances obtained by our parallelization methods are illustrated by solving the CP problems using the Google OR-Tools solver on top of the parallel Bobpp framework.

Cette thèse se situe dans le domaine de la programmation par contraintes (CP). Plus précisément, nous nous intéressons au problème de satisfaction de contraintes pondérées (WCSP), qui est un problème d'optimisation pour lequel plusieurs formes de cohérences locales souples telles que, par exemple, la cohérence d’arc existentielle directionnelle (EDAC*) et la cohérence d’arc virtuelle (VAC) ont été proposées durant ces dernières années. Dans ce cadre, nous adoptons une perspective différente en revisitant la propriété bien connue de la substituabilité. Tout d’abord, nous précisons les relations existant entre la substituabilité de voisinage souple (SNS) et une propriété appelée pcost qui est basée sur le concept de surcoût de valeurs (par le biais de l'utilisation de paires de surcoût). Nous montrons que sous certaines hypothèses, pcost est équivalent à SNS, mais que dans le cas général, elle est plus faible que SNS prouvée être coNP-difficile. Ensuite, nous montrons que SNS conserve la propriété VAC, mais pas la propriété EDAC. Enfin, nous introduisons un algorithme optimisé et nous montrons sur diverses séries d’instances WCSP l’intérêt pratique du maintien de pcost avec AC*, FDAC* ou EDAC*, au cours de la recherche. Nous introduisons un algorithme optimisé et nous étudions la relation existante entre SNS et les différentes cohérences. Nous présentons aussi un nouveau type de propriétés pour les WCSPs. Il s'agit de la cohérence de tuples (TC) dont l'établissement sur un WCN est effectué grâce à une nouvelle opération appelée TupleProject. Nous proposons également une version optimale de cette propriété, OTC, qui peut être perçue comme une généralisation de OSAC (Optimal Soft Arc Consistency). Enfin, nous étendons la notion de substituabilité souple aux tuples. / This thesis is in the field of constraint programming (CP). More precisely, we focus on the weighted constraint satisfaction problem (WCSP), which is an optimization problem for which many forms of soft local (arc) consistencies have been proposed such as, for example, existential directional arc consistency (EDAC) and virtual arc consistency (VAC) in recent years. In this context, we adopt a different perspective by revisiting the well-known property of (soft) substitutability. First, we provide a clear picture of the relationships existing between soft neighborhood substitutability (SNS) and a tractable property called $pcost$ which allows us to compare the cost of two values (through the use of so-called cost pairs). We prove that under certain assumptions, $pcost$ is equivalent to SNS but weaker than SNS in the general case since we show that SNS is coNP-hard. We also show that SNS preserves the property VAC but not the property EDAC. Finally, we introduce an optimized algorithm and we show on various series of WCSP instances, the practical interest of maintaining $pcost$ together with AC*, FDAC* or EDAC*, during search. We also present a new type of properties for WCSPs called tuples consistency (TC). Enforcing TC is done through a new operation called TupleProject. Moreover, we propose an optimal version of this property, OTC, which can be seen as a generalization of OSAC (Optimal Soft Arc Consistency). Finally, we extend soft substitutability concept to tuples.

Bien que le domaine des systèmes multi-agents ait été largement étudié, les interactions entre agents entraînent des pertes de privacité. En effet, la résolution de problèmes distribués, étant fréquemment combinatoires, impose un échange intensif d’informations entre les agents jusqu’à l’obtention d’un accord. Le problème est que les approches existantes ne considèrent généralement pas la confidentialité des données et se concentrent surtout sur la satisfaction des contraintes des agents pour évaluer les solutions. Les travaux présentés dans cette thèse visent donc à prendre en compte de façon principielle la problématique de la privacité dans le raisonnement distribué. Nous montrons que les travaux existants dans le domaine permettent toutefois aux agents de préserver implicitement un certain degré de privacité. Nous proposons une approche basée sur la théorie de l’utilité, un cadre formel bien défini en Intelligence Artificielle, permettant une approche objective et quantitative des intérêts et comportements raisonnables des agents. Plus précisément, le modèle que nous avons développé inclut non seulement les paramètres habituels mais également l’information sur la privacité des agents quantifiée en termes d’utilité. Nous montrons aussi que ces problèmes doivent être envisagés comme des problèmes de planification où les agents choisissent des actions maximisant leur utilité. Des algorithmes actuels peuvent être décrits comme des plans utilisables comme modèle générique par des planificateurs intelligents. Les expérimentations réalisées ont permis de valider l’approche et d’évaluer la qualité des solutions obtenues tout en montrant que leur efficacité peut être accrue à l’aide de traitements de privacité. / Although the field of multi-agent systems has been largely studied, interactions between agents imply privacy loss. Indeed, solving distributed problems, being frequently combinatorial, implies an extensive exchange of information between agents until an agreement is found. The problem is that existing approaches do not generally consider privacy and focus only on the satisfaction of agents’ constraints to evaluate solution. The works presented in this thesis therefore aim at considering systematically the issue of privacy in distributed reasoning. We show that existing works in the field still let agents preserve implicitly some degree of privacy. We propose an approach based on utility theory, a formal setting well defined in Artificial Intelligence, allowing an objective and quantitative approach to the interests and reasonable behaviours of agents. More precisely, the model we have developed includes non only the usual parameters but also information on agents privacy quantified in term of utility. We also show that these problems must be considered as planning problems where agents choose actions maximizing their utility. Common algorithms can be described as plans usable as generic models by intelligent planners. Conducted experiments let us validate the approach and evaluate the quality of obtained solution, while showing that their efficiency can be improved thanks to privacy considerations.

Dans un contexte applicatif de surveillance de zone maritime, nous voulons fournir à un opérateur humain des informations sémantiquement riches et dynamiques relatives aux comportements des entités sous surveillance. Réussir à relier les mesures brutes en provenance d’un système de capteurs aux descriptions abstraites de ces comportements est un problème difficile. Ce dernier est d’ailleurs en général traité en deux temps: tout d’abord, réaliser un prétraitement sur les données hétérogènes, multidimensionnelles et imprécises pour les transformer en un flux d’évènements symbolique, puis utiliser des techniques de reconnaissance de plans sur ces mêmes évènements. Ceci permet de décrire des étapes de plans symboliques de haut niveau sans avoir à se soucier des spécificités des capteurs bas niveau. Cependant, cette première étape est destructrice d’information et de ce fait génère une ambigüité supplémentaire dans le processus de reconnaissance. De plus, séparer les tâches de reconnaissance de comportements est générateur de calculs redondants et rend l’écriture de la bibliothèque de plans plus ardue. Ainsi, nous proposons d’aborder cette problématique sans séparer en deux le processus de reconnaissance. Pour y parvenir, nous proposons un nouveau modèle hiérarchique, inspiré de la théorie des langages formels, nous permettant de construire un pont au-dessus du fossé sémantique séparant les mesures des capteurs des intentions des entités. Grâce à l’aide d’un ensemble d’algorithmes manipulant ce modèle, nous sommes capables, à partir d’observations, de déduire les plausibles futures évolutions de la zone sous surveillance, tout en les justifiant des explications nécessaires. / In a maritime area supervision context, we seek providing a human operator with dynamic information on the behaviors of the monitored entities. Linking raw measurements, coming from sensors, with the abstract descriptions of those behaviors is a tough challenge. This problem is usually addressed with a two-stepped treatment: filtering the multidimensional, heterogeneous and imprecise measurements into symbolic events and then using efficient plan recognition techniques on those events. This allows, among other things, the possibility of describing high level symbolic plan steps without being overwhelmed by low level sensor specificities. However, the first step is information destructive and generates additional ambiguity in the recognition process. Furthermore, splitting the behavior recognition task leads to unnecessary computations and makes the building of the plan library tougher. Thus, we propose to tackle this problem without dividing the solution into two processes. We present a hierarchical model, inspired by the formal language theory, allowing us to describe behaviors in a continuous way, and build a bridge over the semantic gap between measurements and intents. Thanks to a set of algorithms using this model, we are able, from observations, to deduce the possible future developments of the monitored area while providing the appropriate explanations.

Ce travail s’inscrit dans le domaine de l’ordonnancement à base de programmation par contraintes. Dans ce cadre, la contrainte de ressource la plus fréquemment rencontrée est la cumulative, qui permet de modéliser des processus se déroulant de manière parallèle.Nous étudions dans cette thèse la contrainte cumulative en nous aidant d’outils rarement utilisés en programmation par contraintes (analyse polyédrale, dualité de la programmation linéaire, dualité de la géométrie projective) et proposons deux contributions pour le domaine.Le renforcement cumulatif est un moyen de générer des contraintes cumulatives redondantes plus serrées, de manière analogue à la génération de coupes en programmation linéaire entière. Il s'agit ici de l'un des premiers exemples de contrainte globale redondante.Le Raisonnement Énergétique est une propagation extrêmement puissante pour la contrainte cumulative, avec jusque-là une complexité élevée en O(n^{3}). Nous proposons un algorithme qui calcule cette propagation avec une complexité O(n^{2}log n), ce qui constitue une amélioration significative de cet algorithme connu depuis plus de 25 ans. / This work falls in the scope of constraint-based scheduling. In this framework, the most frequently encountered resource constraint is the cumulative, which enables the modeling of parallel processes.In this thesis, we study the cumulative constraint with the help of tools rarely used in constraint programming (polyhedral analysis, linear programming duality, projective geometry duality) and propose two contributions for the domain.Cumulative strengthening is a means of generating tighter redundant cumulative constraints, analogous to the generation of cuts in integer linear programming. This is one of the first examples of a redundant global constraint.Energy Reasoning is an extremely powerful propagation for cumulative constraint, with hitherto a high complexity of O(n^{3}). We propose an algorithm that computes this propagation with a O(n^{2}log n) complexity, which is a significant improvement of this algorithm known for more than 25 years.

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.

L'activité de conception est un processus complexe et décisif dans le cycle de vie des produits et des procédés de fabrication. Dans le contexte actuel, les chercheurs et ingénieurs de conception notent une nette augmentation de la complexité des produits et procédés, pour satisfaire au mieux l’ensemble des exigences croissantes provenant de l’ensemble des acteurs du cycle de vie (industriels et utilisateurs) mais aussi du monde normatif. La gestion des connaissances et de l’expertise métier est un atout important pour rendre plus efficace et accélérer ce processus. Les recherches actuelles sur la gestion des connaissances font émerger des méthodes et outils performants pour identifier, formaliser, exploiter et diffuser la connaissance et les expériences issues de conceptions passées en vue de produire rapidement de nouvelles solutions. Parmi les approches existantes le Raisonnement à Partir de Cas (RàPC) et la Programmation Par Contraintes (PPC) correspondent aux besoins identifiés en Génie des Procédés. A partir de l’analyse de ces deux approches, ce travail propose un couplage du RàPC et de la PPC afin de fournir un cadre méthodologique et un outil logiciel pour une aide à la conception. Le RàPC permet de capitaliser et de remémorer les expériences passées. Toutefois, la modification de la solution passée pour répondre aux exigences du nouveau problème nécessite l’ajout de nouvelles connaissances aussi appelées connaissances d’adaptation. La PPC, quant à elle, offre justement un cadre approprié pour modéliser et gérer la connaissance permettant l’obtention d’une solution à un problème mais aussi ces connaissances d’adaptation. Outre la formalisation des connaissances d’adaptation, une des difficultés réside dans l’acquisition de ces connaissances. Dans l’approche proposée, le cycle traditionnel du RàPC a été modifié de façon à créer une boucle d’interaction avec l’utilisateur. Lorsqu’un échec d’adaptation se produit, cette boucle est activée et l’expert est sollicité pour apporter les modifications nécessaires à l’obtention d’une solution appropriée. Cette correction est l’occasion d’acquérir en ligne cette nouvelle connaissance, qui sera par la suite mise à jour et ajoutée dans le système. Un cas d’étude sur la conception d’une opération unitaire de génie des procédés permet d’illustrer l’approche. / Design is a complex and crucial process within the lifecycle of products and production processes. In the current context, design engineers and researchers notice an increasing in complexity of products and processes, in order to meet all the requirements coming from all the participants(manufacturers and users alike) in the life cycle and in the normative world as well. Knowledge management is an important asset to accelerate this process and improve its efficiency. Current research on knowledge management is producing new methods and tools to identify, formalize, exploit and disseminate knowledge from past designs experiences to produce new solutions rapidly. Among existing approaches, Case-Based Reasoning (CBR) and Constraint Programming (CP) are suited to needs identified in Process Engineering. Based on the analysis of these two approaches, this work proposes a coupling of CBR and the CP to provide a methodological framework and a software tool to assist design. The CBR allows to capitalize and retrieve past experiences. However, transforming the past solution to fit the new problem requirements needs the addition of new knowledge also known as Adaptation Knowledge. CP, meanwhile, offers an appropriate framework to model and manage knowledge required to obtain an appropriate solution to a problem, but also the adaptation knowledge. In addition to the formalization of adaptation knowledge, one of the remaining major difficulties lies in knowledge acquisition. In the proposed approach, the traditional CBR cycle has been modified to create a user interaction loop. When an adaptation failure occurs, this loop is activated and the expert is asked to make the necessary changes to achieve an appropriate solution. This correction is an opportunity to acquire this new knowledge online, which will be subsequently updated and added into the system. A case study on the design of a unit operation of Process Engineering is used to illustrate the approach

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.