Search

The National Research Council of Canada (NRC) is committed to supporting the scale ai cluster's goals through its Artificial Intelligence for Logistics program, which includes convener support in supply chain and logistics. The program also provides R&D expertise focused on next-generation technology issues to ensure Canadian excellence in logistics for the longer term. Using its national reach, the NRC program is creating linkages between stakeholders, and enabling the advancement of the technologies and firms that will make supply chain and logistics excellence a competitive advantage for Canada., Le Conseil national de recherches du Canada (CNRC) s'est engagé à appuyer les objectifs de la grappe scale ai par l'entremise de son programme Intelligence artificielle au service de la logistique, reliant des organisations dans les domaines de la chaine d'approvisionnement et de la logistique. Le programme tire parti d'une expertise en R-D axée sur les enjeux technologiques de la prochaine génération afin d'assurer l'excellence de la logistique canadienne à long terme. Fort de sa portée nationale, le programme crée des liens entre les intervenants et permet l'avancement des technologies et des entreprises qui fera de l'excellence dans la gestion de la chaîne d'approvisionnement et de la logistique un avantage concurrentiel pour le Canada.

En informatique, la résolution de problèmes NP-difficiles en un temps raisonnable est d’une grande importance : optimisation de la chaîne d’approvisionnement, planification, routage, alignement de séquences biologiques multiples, inference dans les modèles graphiques pro- babilistes, et même certains problèmes de cryptographie sont tous des examples de la classe NP-complet. En pratique, nous modélisons beaucoup d’entre eux comme un problème d’op- timisation en nombre entier, que nous résolvons à l’aide de la méthodologie séparation et évaluation. Un algorithme de ce style divise un espace de recherche pour l’explorer récursi- vement (séparation), et obtient des bornes d’optimalité en résolvant des relaxations linéaires sur les sous-espaces (évaluation). Pour spécifier un algorithme, il faut définir plusieurs pa- ramètres, tel que la manière d’explorer les espaces de recherche, de diviser une recherche l’espace une fois exploré, ou de renforcer les relaxations linéaires. Ces politiques peuvent influencer considérablement la performance de résolution. Ce travail se concentre sur une nouvelle manière de dériver politique de recherche, c’est à dire le choix du prochain sous-espace à séparer étant donné une partition en cours, en nous servant de l’apprentissage automatique profond. Premièrement, nous collectons des données résumant, sur une collection de problèmes donnés, quels sous-espaces contiennent l’optimum et quels ne le contiennent pas. En représentant ces sous-espaces sous forme de graphes bipartis qui capturent leurs caractéristiques, nous entraînons un réseau de neurones graphiques à déterminer la probabilité qu’un sous-espace contienne la solution optimale par apprentissage supervisé. Le choix d’un tel modèle est particulièrement utile car il peut s’adapter à des problèmes de différente taille sans modifications. Nous montrons que notre approche bat celle de nos concurrents, consistant à des modèles d’apprentissage automatique plus simples entraînés à partir des statistiques du solveur, ainsi que la politique par défaut de SCIP, un solveur open-source compétitif, sur trois familles NP-dures: des problèmes de recherche de stables de taille maximum, de flots de réseau multicommodité à charge fixe, et de satisfiabilité maximum., In computer science, solving NP-hard problems in a reasonable time is of great importance, such as in supply chain optimization, scheduling, routing, multiple biological sequence align- ment, inference in probabilistic graphical models, and even some problems in cryptography. In practice, we model many of them as a mixed integer linear optimization problem, which we solve using the branch and bound framework. An algorithm of this style divides a search space to explore it recursively (branch) and obtains optimality bounds by solving linear relaxations in such sub-spaces (bound). To specify an algorithm, one must set several pa- rameters, such as how to explore search spaces, how to divide a search space once it has been explored, or how to tighten these linear relaxations. These policies can significantly influence resolution performance. This work focuses on a novel method for deriving a search policy, that is, a rule for select- ing the next sub-space to explore given a current partitioning, using deep machine learning. First, we collect data summarizing which subspaces contain the optimum, and which do not. By representing these sub-spaces as bipartite graphs encoding their characteristics, we train a graph neural network to determine the probability that a subspace contains the optimal so- lution by supervised learning. The choice of such design is particularly useful as the machine learning model can automatically adapt to problems of different sizes without modifications. We show that our approach beats the one of our competitors, consisting of simpler machine learning models trained from solver statistics, as well as the default policy of SCIP, a state- of-the-art open-source solver, on three NP-hard benchmarks: generalized independent set, fixed-charge multicommodity network flow, and maximum satisfiability problems.

The domain of energy management involves many combinatorial optimization problems known to be computationally hard. The emergence of quantum computers suggests new approaches for these problems. For near-future machines particularly promising are variational quantum heuristics such as QAOA that can leverage the computational power of the imperfect quantum hardware. We explore the potential of variational quantum algorithms for optimization problems issued from the field of "smart charging"}of electrical vehicles. We consider two problems inspired by real-world usecases. In the first problem, modeled as Max-K-Cut, we search to schedule a set of prioritized charges on several stations while minimizing the weighted completion time. In the second problem, modeled as Maximum Independent Set, we aim to maximize the number of satisfied charge demands on a single station while respecting the conflicts between demands. For both problems, we develop an experimental protocol specifying the encoding step and the parameter optimization routine. Our numerical experiments confirm the interest of quantum heuristics for these problems as well as the quality of our experimental protocol. In order to extend the applicability of quantum heuristics beyond QUBO we introduce a new hybrid approach that integrates quantum routines in the classical Branch & Price algorithm for large integer linear programs. We test this approach on a smart charging problem that is modeled as graph coloring problem. Our computational results affirm the potential of the hybrid approach while revealing the considerable dependence of the performance gain on the particular instance of the problem. Important components of variational algorithms can be represented as ZX-diagrams. We demonstrate how the rewriting rules of ZX-calculus can be used to derive the analytical formula for the mean energy of a general Ising model in a QAOA of depth 1 state. Furthermore, we contribute to the theoretical exploration of variational algorithms by extending the ZX-calculus with addition and differentiation of ZX-diagrams. Our inductive procedure for the addition is fully diagrammatic. For the differentiation we suggest two approaches. The first approach is inductive, it leverages our procedure for addition to explicitly represent the product rules. The second approach is resumed in two formulas derived from the factored form of parameterized diagrams.; Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.

Manufacturers must efficiently manage their production capacities and their performances to satisfy customer demands with quality goods. They also have been constantly challenged to optimize resource usage and production performance in a dynamic and volatile market context in a cost effective manner. To achieve this business objective, we consider lot-sizing problems under yield uncertainty via a robust, adaptive robust and distributionally robust optimization methodologies to determine the production setups and quantities that meet demands with quality goods, while minimizing the overall productionand inventory management costs. We propose different models and methodological strategies to compute optimal robust and less conservative production plans. We also provide a risk analysis to help decision-makers to tailor their decision plans to their strategic and operational goals. The experimental results show that robust-wise production plans have a better cost cutting strategy compared with other resolution approaches. The computational experiments show the robustness and effectiveness of the robust model through an average and worst case analysis. The experiments also demonstrate the performances and the value of the adaptive robust solutions and thelow sensitiveness to errors in predictions of the distributionally robust models.; Les fabricants doivent gérer leurs capacités de production et leur performance pour satisfaire la demande des clients avec des produits de qualité. De plus, ils sont constamment mis au défi d’optimiser l’utilisation de leurs ressources et leur performance de production dans un contexte de marché dynamique et volatil, et ce, de manière rentable. Pour atteindre cet objectif commercial, un défi tactique à relever parmi d’autres, les fabricants doivent minutieusement prendre des décisions de dimensionnement de lots de production afin de déterminer la configuration et les quantités de production répondant aux demandes avec des produits de qualité, tout en minimisant les coûts globaux de production et de gestion de stocks. Nous proposons différents modèles et stratégies méthodologiques pour calculer des plans de production optimaux robustes à conservation moindre. Nous fournissons également une analyse de risque pour aider les décideurs à adapter leurs plans décisionnels à leurs objectifs stratégiques et opérationnels. Les résultats expérimentaux montrent que les plans de production robustes ont une meilleure stratégie de réduction des coûts par rapport aux autres approches de résolution. Les expériences numériques montrent la robustesse et l’efficacité du modèle robuste à travers une analyse des cas moyens et les plus défavorables. Les expériences démontrent également les performances et la valeur des solutions adaptatives robustes et la faible sensibilité aux erreurs de prédiction des modèles distributionnellement robustes.

The field of Artificial Intelligence (AI) has brought a broad impact on today's society, leading to a gripping interaction between several scientific disciplines. In this respect, there has been a strong twofold interest across the literature.On the one hand, a growing trend in telecommunication networks consists in revisiting classic optimization problems using machine learning techniques in order to exploit their potential benefits. We focus on some challenges brought by the detection of anomalies in networks, and the allocation of resources within software-defined networking (SDN) and network function virtualization (NFV).On the other hand, a substantial effort has been devoted towards the theoretical understanding of the collective behavior of networks. We focus on some challenges brought by the study of majority dynamics within multi-agent systems, and the compression of artificial neural networks with the aim at increasing their efficiency.In this study, we contextualize the above focal points in the framework of investigating some foundations of networks; viewed through the lens of telecommunications networks and neural networks. We first focus our attention on developing graph similarity measures for network anomaly detection. Next, we study deterministic and stochastic majority dynamics in multi-agent systems. Then, we discuss the random subset sum problem in the context of neural network compression. Finally, we walk through some other miscellaneous problems.; Le domaine de l'Intelligence Artificielle (IA) a un large impact sur la société d'aujourd'hui, ayant conduit notamment à une interaction passionnante entre plusieurs disciplines scientifiques. À cet égard, un double intérêt émerge dans la littérature.D'une part, une tendance croissante dans les réseaux de télécommunication consiste à revisiter les problèmes d'optimisation classiques en utilisant des techniques d'apprentissage automatique afin d'exploiter leurs avantages potentiels. Nous nous focaliserons sur certains défis posés par la détection d'anomalies dans les réseaux ainsi que l'allocation des ressources dans le cadre des réseaux logiciels (SDN) et de la virtualisation des fonctions réseau (NFV). D'autre part, un effort substantiel a été consacré dans le but d'apporter une compréhension théorique du comportement collectif des réseaux. Nous nous focaliserons sur certains défis posés par l'étude de la dynamique majoritaire au sein des systèmes multi-agents ainsi qu'à la compression des réseaux de neurones artificiels dans le but d'augmenter leur efficacité.Dans cette étude, nous contextualisons les points focaux ci-dessus dans le cadre de l'étude de certains fondements de réseaux; vus sous l'angle des réseaux de télécommunications et des réseaux neuronaux. Nous nous concentrons d'abord sur le développement de mesures de similarité de graphes pour la détection d'anomalies dans les réseaux. Ensuite, nous étudions la dynamique majoritaire déterministe et stochastique dans les systèmes multi-agents. Ensuite, nous discutons du problème de la somme de sous-ensembles aléatoires dans le contexte de la compression des réseaux neuronaux. Enfin, nous passons en revue quelques problèmes généraux divers.

L’optimisation de processus complexes fait l’objet d’études en Recherche Opérationnelle et Optimisation Mathématique. Mes travaux en optimisation se sont concentrés sur deux types d’application : les problèmes d’ordonnancement et les problèmes issus du spatial. Parmi les problèmes d’ordonnancement, les problèmes cycliques correspondent à ceux pour lesquelles les tâches se répètent périodiquement. Ces problèmes ont été étudiés dans la littérature mais la plupart des travaux considèrent des paramètres déterministes. Pourtant, des incertitudes, comme la durée d’execution des tâches, peuvent survenir. Mes travaux sur l’ordonnancement cyclique visent à considérer ces incertitudes sous la forme d’un problème d'optimisation robuste bi-niveau. Une méthode de résolution basée sur une décomposition de Benders pour la version flexible du problème d'ordonnancement cyclique constitue une autre contribution dans ce domaine. Concernant les problématiques du spatial, les technologies modernes posent de nouveaux problèmes d’optimisation que nous tentons de résoudre tels que l’optimisation du placement de faisceau d’un satellite de télécommunication. Pour résoudre ce problème, nous proposons un encadrement paramétrable de la norme euclidienne dans le plan.

International audience; Pour un utilisateur qui n'est pas un développeur expert en recherche opérationnelle, un système d'optimisation est souvent perçu comme une boîte noire qui, étant donnée une instance d'un problème, fournit une solution qu'il convient de suivre. Dans ce contexte, l'utilisateur peut vouloir interroger le système quant à la pertinence d'une solution qu'il aurait retourné et obtenir des explications de sa part, que ce soit pour avoir davantage confiance en cette solution avant de la suivre ou simplement pour être critique vis-à-vis de celle-ci.Expliquer des solutions obtenues au moyen de systèmes d'optimisation n'est pas une tâche facile et soulève de nombreuses questions. Que peut-on expliquer ? Comment calculer le contenu d'une explication ? Qu'est-ce qu'un calcul d'explication efficace? Comment présenter une explication? Qu'est-ce qu'une explication intelligible pour l'utilisateur ? Etc. Nous proposons de s'intéresser à cette problématique de l'explication de solutions dans le cas d'une application : le problème de planification d'employés mobiles.

Nous considérons le problème de l'arbre couvrant budgeté avec une approche basée sur la programmation mathématique. Les contraintes de sac à dos vont venir modifier la structure du polyèdre de l'arbre couvrant. L'objectif principal de notre travail est detrouver des formulations étendues ainsi que des inégalités valides et facettes afin de concevoir des algorithmes de branchements efficaces pour résoudre ces problèmes de réseaux budgétés.

Online influence is the plinth of the social networks’ effect in our lives and its impact has been steeply increasing. From viral marketing to political campaigns and from news adoption to disease transmission, the way we are influenced by others is more prevalent than ever. In this thesis, we address the problem of efficiently learning and analyzing influence representations for numerous graph mining problems that are apropos.The first half of the thesis is devoted to the problem of influence maximization, an NP-hard combinatorial optimization problem. The aim is to find the nodes in a network that can maximize the spread of information, where the spread is typically defined by random influence probabilities and simple diffusion models. To address this, in the thesis' first part, we devise a node representation learning model based on diffusion cascades along with an adaptation of a traditional influence maximization algorithm that utilizes the output of the model. This framework surpasses competitive methods, evaluated in terms of computational time and the influence of the predicted seeds in cascades of the immediate future.The second part is devoted to learning how to perform influence maximization. We develop a graph neural network that inherently parameterizes an upper bound of influence estimation, and train it on small simulated graphs. We experimentally show that it can provide accurate estimations faster than the alternatives for graphs 10 times larger than the train set. Furthermore, we use the models’ predictions and representations to propose three new influence maximization methods. An adaptation of Cost Effective Lazy Forward that surpasses SOTA but with significant computational overhead, a Q-learning model that learns to retrieve seeds sequentially, and a submodular function that acts as proxy for the marginal gain and can be optimized adaptively and greedily with a theoretical guarantee. The latter strikes the best balance between efficiency and accuracy in our experiments.In the second half of the thesis, we focused on specific applications of influence in real data. In the third part we approach epidemic forecasting using influence learning. We utilize the inherent message passing of Graph Neural Networks to learn node representations based on mobility networks of a country’s regions and the history of the disease progression. These representations aim to capture how the epidemic diffuses through regions, and are used to predict the number of new COVID-19 cases with a forecasting window of up to 14 days. Furthermore, to capitalize on the lag of the COVID-19 spreading between countries, a meta-learning algorithm is proposed to transfer knowledge between models trained in some countries’ whole epidemic circle, to a model predicting cases for another country at the start of the outbreak, where the available training data is limited. Our approach outperforms baseline, time-series, and other deep learning models.In the final part, we analyze different versions of academic influence and device methods to quantify and predict it. Initially we utilize the Microsoft Academic Graph to build an author-citation network with billions of edges. We subsample it and perform directed-core decomposition to quantify it and visualize it through an interactive web-app. Subsequently we experiment with classifying the h-index of an author based on a GNN on her coauthorship graph and the text of her papers.We conclude the thesis with future directions regarding learning-based influence maximization with heterogeneous data and efficient neural network training through submodular active learning., L'influence en ligne est le socle de l'effet des réseaux sociaux sur nos vies et son impact n'a cessé de croître. Du marketing viral aux campagnes politiques à la transmission de maladies, la façon dont nous sommes influencés par les autres est plus répandue que jamais. Dans cette thèse, nous abordons le problème de l'apprentissage et de l'analyse efficaces des représentations d'influence pour de nombreux problèmes d'exploration de graphes qui sont à propos.La première moitié de la thèse est consacrée au problème de la maximisation de l'influence, un problème NP d'optimisation combinatoire. L'objectif est de trouver les nœuds d'un réseau qui peuvent maximiser la propagation de l'information, où la propagation est typiquement définie par des probabilités d'influence aléatoires et des modèles de diffusion simples. Pour répondre à ce problème, nous concevons un modèle d'apprentissage de la représentation des nœuds basé sur des cascades de diffusion ainsi qu'une adaptation d'un algorithme traditionnel de maximisation de l'influence qui utilise la sortie du modèle. Ce cadre surpasse les méthodes concurrentes, évaluées en termes de temps de calcul et d'influence des graines prédites dans les cascades du futur immédiat.La prochaine partie est consacrée à l'apprentissage de la maximisation de l'influence. Nous développons un réseau neuronal de graphe qui paramètre de manière inhérente une limite supérieure d'estimation de l'influence, et nous l'entraînons sur de petits graphes simulés. Nous montrons expérimentalement qu'il peut fournir des estimations précises plus rapidement que les autres solutions pour des graphes /dix/ fois plus grands que l'ensemble d'entraînement. En outre, nous utilisons les prédictions et les représentations des modèles pour proposer nouvelles méthodes de maximisation de l'influence. Une adaptation de un ancien algorithme, un modèle de Q-learning, et une fonction submodulaire qui agit comme un proxy pour le gain marginal et peut être optimisée de manière adaptative et avide avec certaines garanties théoriques. Cette dernière fonction offre le meilleur équilibre entre efficacité et précision.Dans la deuxième moitié de la thèse, nous sommes concentrés sur des applications spécifiques de l'influence. Nous abordons la prévision des épidémies en utilisant l'apprentissage par influence. Nous utilisons le passage de messages inhérent aux réseaux neuronaux graphiques pour apprendre des représentations de nœuds basées sur les réseaux de mobilité des régions d'un pays et l'histoire de la contagion. Ces représentations sont utilisées pour prédire le nombre de nouveaux cas de COVID-19 avec une fenêtre de prévision allant jusqu'à 14 jours. En outre, pour tirer parti du décalage de la propagation entre les pays, un algorithme de méta-learning est proposé pour transférer les connaissances entre les modèles formés dans le cercle épidémique complet de certains pays, à un modèle prédisant les cas pour un autre pays au début de l'épidémie, où les données d'apprentissage disponibles sont limitées. Notre approche surpasse les modèles de référence, les séries temporelles et d'autres modèles d'apprentissage profond.Dans la dernière partie, nous analysons différentes versions de l'influence académique et essayons de la prédire. Dans un premier temps, nous utilisons le MAG pour construire un réseau de citations d'auteurs avec des milliards d'arêtes. Nous le sous-échantillonnons et effectuons une décomposition en noyaux dirigés pour le quantifier et le visualiser au moyen d'une application web interactive. Ensuite, nous expérimentons la classification du h-index d'un auteur sur la base d'un GNN sur son graphe de coauteurs et le texte de ses articles. Nous concluons la thèse en abordant de futures directions concernant la maximisation de l'influence basée sur l'apprentissage avec des données hétérogènes et l'entraînement efficace des réseaux neuronaux par l'apprentissage actif submodulaire.

This thesis integrates machine learning techniques into meta-heuristics for solving combinatorial optimization problems. This integration aims to guide the meta-heuristics toward making better decisions and consequently make meta-heuristics more efficient and improve their performance in terms of solution quality and convergence rate. This thesis, first, provides a comprehensive yet technical review of the literature and proposes a unified taxonomy on different ways of the integration. For each type of integration, a complete analysis and discussion is provided on technical details, including challenges, advantages, disadvantages, and perspectives. From a technical aspect, we then focus on a particular integration and address the problem of adaptive operator selection in meta-heuristics using reinforcement learning techniques. More precisely, we propose a general framework that integrates the Q-learning algorithm, as a reinforcement learning algorithm, into the iterated local search algorithm to adaptively and dynamically select the most appropriate search operators at each step of the search process based on their history of performance. The proposed framework is finally applied on two combinatorial optimization problems, traveling salesman problem and permutation flowshop scheduling problem. In both applications, the framework better performance in terms of solution quality and convergence rate compared to a random selection of operators, especially for large size instances of the problems. Moreover, we observe that the proposed framework shows the state-of-the-art behavior when solving the permutation flowshop scheduling problem., Cette thèse intègre des techniques d'apprentissage automatique dans des méta-heuristiques pour résoudre des problèmes d'optimisation combinatoire. Cette intégration guidera les méta-heuristiques vers la prise de meilleures décisions et par conséquent à rendre les méta-heuristiques plus efficaces. Cette thèse, tout d'abord, fournit une revue complète mais technique de la littérature et propose une taxonomie unifiée sur les différentes manières d'intégration. Pour chaque type d'intégration, une analyse et une discussion complètes sont fournies sur les détails techniques, y compris les défis, les avantages, les inconvénients et les perspectives. Nous nous concentrons ensuite sur une intégration particulière et abordons le problème de la sélection adaptative des opérateurs dans les méta-heuristiques utilisant des techniques d'apprentissage par renforcement. Plus précisément, nous proposons un cadre général qui intègre l'algorithme Q-learning dans l'algorithme de recherche locale itérée afin de sélectionner de manière adaptative les opérateurs de recherche les plus appropriés à chaque étape du processus de recherche en fonction de leur historique de performance. Le cadre proposé est appliqué à deux problèmes d'optimisation combinatoire, le problème du voyageur de commerce et le problème d'ordonnancement de type flowshop de permutation. Dans les deux applications, le cadre proposé est plus performant en termes de qualité de solution et de taux de convergence qu'une sélection aléatoire d'opérateurs. De plus, nous observons que le cadre proposé montre un comportement d’état de l’art lors de la résolution du problème d'ordonnancement des flux de permutation.

Discrete Graphical Models (GMs) represent joint functions over large sets of discrete variables as a combination of smaller functions. There exist several instantiations of GMs, including directed probabilistic GMs like Bayesian Networks (BNs) and undirected deterministic models like Cost Function Networks (CFNs). Queries like Most Probable Explanation (MPE) on BNs and its equivalent on CFNs, which is cost minimisation, are NP-hard, but there exist robust solving techniques which have found a wide range of applications in fields such as bioinformatics, image processing, and risk analysis. In this thesis, we make contributions to the state of the art in learning the structure of BNs, namely the Bayesian Network Structure Learning problem (BNSL), and answering MPE and minimisation queries on BNs and CFNs. For BNSL, we discover a new point in the design space of search algorithms, which achieves a different trade-off between inference strength and speed of inference. Existing algorithms for it opt for either maximal strength of inference, like the algorithms based on Integer Programming (IP) and branch-and-cut, or maximal speed of inference, like the algorithms based on Constraint Programming (CP). We specify properties of a specific class of inequalities, called cluster inequalities, which lead to an algorithm that performs much stronger inference than that based on CP, much faster than that based on IP. We combine this with novel ideas for stronger propagation and more compact domain representations to achieve state-of-the-art performance in the open-source solver ELSA (Exact Learning of bayesian network Structure using Acyclicity reasoning). For CFNs, we identify a weakness in the use of linear programming relaxations by a specific class of solvers, which includes the award-winning open-source ToulBar2 solver. We prove that this weakness can lead to suboptimal branching decisions and show how to detect maximal sets of such decisions, which can then be avoided by the solver. This allows ToulBar2 to tackle problems previously solvable only by hybrid algorithms., Les modèles graphiques discrets représentent des fonctions jointes sur de grands ensembles de variables en tant qu'une combinaison de fonctions plus petites. Il existe plusieurs instanciations de modèles graphiques, notamment des modèles probabilistes et dirigés comme les réseaux Bayésiens, ou des modèles déterministes et non-dirigés comme les réseaux de fonctions de coûts. Des requêtes comme trouver l'explication la plus probable (MPE) sur un réseau Bayésiens, et son équivalent, trouver une solution de coût minimum sur un réseau de fonctions de coût, sont toutes les deux des tâches d’optimisation combinatoire NP-difficiles. Il existe cependant des techniques de résolution robustes qui ont une large gamme de domaines d'applications, notamment les réseaux de régulation de gènes, l'analyse de risques et le traitement des images. Dans ce travail, nous contribuons à l'état de l'art de l'apprentissage de la structure des réseaux Bayésiens (BNSL), et répondons à des requêtes de MPE et de minimisation des coûts sur les réseaux Bayésiens et les réseaux de fonctions de coûts. Pour le BNSL, nous découvrons un nouveau point dans l'espace de conception des algorithmes de recherche qui atteint un compromis différent entre la qualité et la vitesse de l'inférence. Les algorithmes existants optent soit pour la qualité maximale de l'inférence en utilisant la programmation linéaire en nombres entiers (PLNE) et la séparation et évaluation, soit pour la vitesse de l'inférence en utilisant la programmation par contraintes (PPC). Nous définissons des propriétés d'une classe spéciale d'inégalités, qui sont appelées "les inégalités de cluster" et qui mènent à un algorithme avec une qualité d'inférence beaucoup plus puissante que celle basée sur la PPC, et beaucoup plus rapide que celle basée sur la PLNE. Nous combinons cet algorithme avec des idées originales pour une propagation renforcée ainsi qu'une représentation de domaines plus compacte, afin d'obtenir des performances dépassant l'état de l'art dans le solveur open source ELSA (Exact Learning of bayesian network Structure using Acyclicity reasoning). Pour les réseaux de fonctions de coûts, nous identifions une faiblesse dans l'utilisation de la relaxation continue dans une classe spécifique de solveurs, y compris le solveur primé "ToulBar2". Nous prouvons que cette faiblesse peut entraîner des décisions de branchement sous-optimales et montrons comment détecter un ensemble maximal de telles décisions qui peuvent ensuite être évitées par le solveur. Cela permet à ToulBar2 de résoudre des problèmes qui étaient auparavant solvables uniquement par des algorithmes hybrides.

International audience; Dans ce papier, on présente un outil, MS-Builder, qui génère des certificats pour le problème Max-SAT, en appelant itérativement un oracle SAT pour générer une réfutation par résolution de la formule qui est ensuite rendue valide pour Max-SAT et appliquée sur la formule. Ce procédé est répété jusqu'à ce que la formule restante devienne satisfiable. On propose également un outil, MS-Checker, capable de vérifier les certificats Max-SAT basés sur l'application de règles d'inférence Max-SAT. Cet article résume les travaux publiés à la conférence SAT 2021 [4].

National audience; Nous proposons un nouvel algorithme pour l’analyse sémantique fondée sur les graphes via le problème de l’arborescence généralisée couvrante.

Mass customization and frequent market fluctuations push industrial companies to employ flexible and reconfigurable multi/mixed-model assembly lines instead of dedicated ones. This thesis focuses on this problem. It concentrates mainly on mixed-model assembly line design and balancing problems. The questions concerning the efficiency of such lines, the importance of optimal task assignment and use of walking workers are asked and studied. To increase the flexibility of the line, we account for different types of task assignments: fixed, model-dependent,and dynamic. We aim to design a line that can handle various entering product models. We use combinatorial optimization methods, and,in particular, robust optimization approaches. We present an extensive literature review on line balancing, workforce planning, and workforce reconfiguration strategies in different production systems. The first problem addresses a configuration selection problem between a single multi-model line and multiple dedicated lines. The second problem consists in designing and balancing a mixed-model assembly line with walking workers. We propose fixed and model-dependent task assignments for a given set of product mixes. The goal is to minimize the total cost of workers and equipment for the worst case. The third problem extends the second one. It considers the dynamic task assignment. In the last problem, we extend the third problem for the case where the sequence of products unfolds takt by takt. In this context, we minimize both the expected total cost and the worst-case cost. In order to solve the considered problems, we develop several exact methods and heuristics: mixed-integer linear programming models, greedy algorithm, local search,matheuristic and fixed-and-optimize heuristics among others. We also apply a Markov Decision Process to the proposed line balancing problem in the last chapter. It is the first study applying this method to a line balancing problem. Computational experiments evaluate the performance of the proposed approaches in terms of solution quality and time consumption. We draw managerial insights in each chapter. Our results show the superiority of the dynamic task assignment compared to model-dependent and fixed ones in different production situations.; Une forte personnalisation de produits et des fréquentes fluctuations du marché poussent les entreprises industrielles à utiliser des lignes d’assemblage à modèles multiples/mixtes, flexibles et reconfigurables plutôt que des lignes dédiées. Cette thèse de doctorat est consacrée à cette problématique. Elle est portée principalement sur la conception et l’équilibrage de lignes d’assemblage à modèles mixtes. Les questions de l’efficacité de telles lignes, l’importance d’affectation optimale de tâches et d’utilisation des opérateurs mobiles sont posées et étudiées. Pour augmenter la flexibilité de la ligne, nous prenons en compte différents types d’affectation des tâches : fixe, dépendant du modèle et dynamique. Nous cherchons à concevoir une ligne qui peut gérer la variété possible de produits entrants. Nous utilisons des techniques d’optimisation combinatoire, et, en particulier, des approches d’optimisation robuste. Nous présentons une revue extensive de la littérature sur l’équilibrage des lignes, la planification des opérateurs et les stratégies de reconfiguration de lignes via la réaffectation des opérateurs. Le premier problème de la thèse porte sur la sélection de configuration entre une ligne unique à multi-modèles et plusieurs lignes dédiées. Le second problème consiste à concevoir et à équilibrer une ligne d’assemblage à modèles mixtes avec des opérateurs mobiles. Nous proposons des affectations de tâches fixes et dépendantes du modèle pour une gamme donnée de produits entrants sur la ligne. L’objectif est de minimiser le coût total de la ligne composé des coûts d’opérateurs et d’équipement dans le pire des cas. Le troisième problème est une extension du deuxième, où les tâches peuvent être affectées de manière dynamique. Enfin, dans le dernier, quatrième problème, nous étendons le troisième problème au cas où la séquence de produits est découverte takt par takt. Dans ce contexte, nous minimisons à la fois l’espérance mathématique de coût total et le coût dans le pire des cas. Afin de résoudre ces problèmes, nous développons plusieurs méthodes exactes et des heuristiques : des modèles de programmation linéaire en variables mixtes, un algorithme glouton, une recherche locale, une matheuristique et une heuristique de type " fixer et optimiser ", entre autres. Nous appliquons également un processus de décision markovien au dernier problème, ce qui représente la première étude qui utilise cette approche pour l’équilibrage de lignes dans la littérature. Des expériences numériques évaluent la performance des modèles proposés en termes de la qualité de solution et du temps de calcul. Nous tirons des conclusions managériales dans chaque chapitre. Nos résultats montrent la supériorité de l’affectation dynamique des tâches par rapport aux affectations fixes et dépendantes de modèle dans différentes situations de production.

In this thesis, we are interested in multi-objective combinatorial optimization, and in particular in evolutionary algorithms based on decomposition. This type of approaches consists in decomposing the original multi-objective problem into multiple single-objective sub-problems that are then solved cooperatively. In this context, we consider the design and the analysis of new algorithmic components contributing to the establishment of the foundations of an optimization framework based on decomposition for multi-objective combinatorial problems known as "black box", i.e., for which the analytical form of the objective functions is not available to the solving algorithm. First of all, we investigate the key components for a better distribution of the computational efforts during the optimization process. To this end, we study the joint impact of the population size and of the number of solutions generated at each iteration, while proposing different strategies for selecting one ore multiple sub-problem(s) to be optimized at each stage. We then study different mechanisms allowing to escape from local optima. They are inspired by techniques from single-objective optimization, and we show they can significantly improve the convergence profile of the considered approaches. Finally, we consider the context of expensive optimization, where the evaluation of each solution is particularly intensive in terms of computational resources. This hence drastically restrict the budget allocated to the optimization process. As such, we investigate new components based on combinatorial meta-models, and we consider their integration within decomposition-based multi-objective evolutionary approaches.; Dans cette thèse, nous nous intéressons à l'optimisation combinatoire multi-objectif, et en particulier aux algorithmes évolutionnaires à base de décomposition. Ce type d'approches consiste à décomposer le problème multi-objectif original en plusieurs sous-problèmes mono-objectifs, qui sont alors résolus de façon coopérative. Dans ce cadre, nous considérons la conception et l'analyse de nouveaux composants algorithmiques contribuant à la mise en place des fondations d'un framework d'optimisation à base de décomposition pour les problèmes combinatoires multi-objectifs dits "boîte-noire", pour lesquels la forme analytique des fonctions objectif n'est pas connue de l'algorithme de résolution. Tout d'abord, nous étudions les éléments clés pour une meilleure répartition des efforts de calculs tout au long du processus d'optimisation. Pour cela, nous étudions l'impact conjoint de la taille de la population et du nombre de solutions générées par itération, tout en proposant différentes stratégies de sélection du ou des sous-problèmes à optimiser à chaque étape. Nous étudions ensuite différents mécanismes permettant de s'échapper des optima locaux. Ceux-ci s'inspirent de techniques issues de l'optimisation mono-objectif et permettent d'améliorer considérablement le profil de convergence des approches considérées. Nous nous plaçons pour finir dans un contexte d'optimisation coûteuse, où l'évaluation de chaque solution s'avère particulièrement gourmande en temps de calcul, ce qui limite considérablement le budget alloué à l'optimisation. Pour cela, nous étudions de nouveaux composants s'appuyant sur des méta-modèles combinatoires, et nous considérons leur intégration au sein d'approches évolutionnaires multi-objectifs basées sur la décomposition.

Dans cette thèse, nous nous intéressons à l'optimisation combinatoire multi-objectif, et en particulier aux algorithmes évolutionnaires à base de décomposition. Ce type d'approches consiste à décomposer le problème multi-objectif original en plusieurs sous-problèmes mono-objectifs, qui sont alors résolus de façon coopérative. Dans ce cadre, nous considérons la conception et l'analyse de nouveaux composants algorithmiques contribuant à la mise en place des fondations d'un framework d'optimisation à base de décomposition pour les problèmes combinatoires multi-objectifs dits "boîte-noire", pour lesquels la forme analytique des fonctions objectif n'est pas connue de l'algorithme de résolution. Tout d'abord, nous étudions les éléments clés pour une meilleure répartition des efforts de calculs tout au long du processus d'optimisation. Pour cela, nous étudions l'impact conjoint de la taille de la population et du nombre de solutions générées par itération, tout en proposant différentes stratégies de sélection du ou des sous-problèmes à optimiser à chaque étape. Nous étudions ensuite différents mécanismes permettant de s'échapper des optima locaux. Ceux-ci s'inspirent de techniques issues de l'optimisation mono-objectif et permettent d'améliorer considérablement le profil de convergence des approches considérées. Nous nous plaçons pour finir dans un contexte d'optimisation coûteuse, où l'évaluation de chaque solution s'avère particulièrement gourmande en temps de calcul, ce qui limite considérablement le budget alloué à l'optimisation. Pour cela, nous étudions de nouveaux composants s'appuyant sur des méta-modèles combinatoires, et nous considérons leur intégration au sein d'approches évolutionnaires multi-objectifs basées sur la décomposition. In this thesis, we are interested in multi-objective combinatorial optimization, and in particular in evolutionary algorithms based on decomposition. This type of approaches consists in decomposing the original multi-objective problem into multiple single-objective sub-problems that are then solved cooperatively. In this context, we consider the design and the analysis of new algorithmic components contributing to the establishment of the foundations of an optimization framework based on decomposition for multi-objective combinatorial problems known as "black box", i.e., for which the analytical form of the objective functions is not available to the solving algorithm. First of all, we investigate the key components for a better distribution of the computational efforts during the optimization process. To this end, we study the joint impact of the population size and of the number of solutions generated at each iteration, while proposing different strategies for selecting one ore multiple sub-problem(s) to be optimized at each stage. We then study different mechanisms allowing to escape from local optima. They are inspired by techniques from single-objective optimization, and we show they can significantly improve the convergence profile of the considered approaches. Finally, we consider the context of expensive optimization, where the evaluation of each solution is particularly intensive in terms of computational resources. This hence drastically restrict the budget allocated to the optimization process. As such, we investigate new components based on combinatorial meta-models, and we consider their integration within decomposition-based multi-objective evolutionary approaches.