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.

Le but de cette thèse est de proposer des méthodes de gestion des approvisionnements adaptées à des contextes particuliers afin de minimiser les coûts logistiques engendrés dans un réseau logistique multi produits, multi niveaux confronté à une demande probabiliste. Au cours de cette thèse, nous nous sommes attachés à : - Proposer des méthodes de gestion des stocks et du transport pour des familles de produits dans différents contextes : - Une première politique de réapprovisionnement est proposée pour une famille de produits caractérisée par une demande aléatoire et répétitive. Cette politique est définie par un niveau de commande et par un niveau de ré-complètement de stock pour chaque produit et une période de réapprovisionnement. Dès qu’un produit atteint le niveau de commande, un réapprovisionnement de tous les produits de la famille est déclenché. - Une deuxième politique de réapprovisionnement est proposée pour une famille de produits caractérisée par une demande très aléatoire et ponctuelle. Cette politique est basée sur les ruptures de stock. A chaque rupture d’un produit présent dans le stock il y a déclenchement d’un réapprovisionnement de tous les produits de la famille. - Proposer une méthode de classification multicritères afin de constituer des groupes de produits relevant d’une politique donnée, chaque classe ou famille regroupant des produits réagissant identiquement. Cette classification des produits en familles homogènes permet d’identifier les caractéristiques déterminantes dans le choix des méthodes de gestion de stock et de transport. - Analyser et comparer les performances de ces deux politiques d’approvisionnement par rapport à des politiques de référence, ainsi que leur sensibilité au regard de quelques paramètres discriminants : variabilité de la demande ; coût des produits ; coût des commandes urgentes… / The aim of this work is to propose methods of inventory management tailored to specific contexts in order to minimize logistics costs incurred in a logistics network multi-product, multi-level faces a probabilistic demand. In my research work, we have focused on the following scientific key-issues: - The proposal of methods of inventory and transportation management for products families in different contexts. The first one is defined to solve the problems identified in a product family characterized by a variable and repetitive demand. This policy is defined by an ordering and a replenishment level for each product and a periodic review. As soon as a product reaches the ordering level, replenishment of the same family products is triggered. • The second one is dedicated to a product family which is characterized by a very punctual and variable demand. This policy is based on inventory shortages. Each shortage of a product in store triggers replenishment of all products of the same family. - The proposal of a multi-criteria classification method in order to select the suitable inventory management method according to specificities of the product and the demand - The analysis and performance comparison of the two procurement policies proposed with standard policies, and their sensitivity with respect to some parameters discriminating: demand variability, cost of products, cost of rush orders.