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.

Cleaning debris in urban areas after major disasters is very relevant to inhabitants to recover from their effects. In natural disasters, an unexpected and large area can be affected. Moreover, the time and the costs to perform the cleaning operations can be very high. In this work, the integrated multi-period scheduling routing problem to clean debris (SRP-CD) after major disasters is investigated. The problem includes strategical (scheduling) and operational (routing) decisions, considering complex issues such as two levels of synchronization between work-troops and dump trucks, and between dump trucks necessary to load, transport and unload debris during limited working days. The goal of SRP-CD is twofold: minimizing the number of days for the overall cleaning, in the strategical level; and minimizing the total costs of vehicle routes in the operational level. A new mathematical model based on a dynamic multi-flow formulation, constructive heuristics, Large Neighborhood Search (LNS)-based metaheuristics and hybrid metaheuristics based on LNS and Simulated Annealing are proposed. Comparison experiments for the model and the approaches are carried out to measure performance and robustness of the proposed methods. To the best of our knowledge, these are the first contributions in the literature for SRP-CD, including all the aspects addressed in this thesis.; Le nettoyage des débris dans les zones urbaines après des catastrophes majeures est très important pour permettre aux habitants de se remettre de leurs effets. Lors de catastrophes, une zone inattendue et étendue peut être touchée. De plus, le temps et les coûts pour effectuer les opérations de nettoyage peuvent être très élevés. Cette thèse aborde le problème intégré multi-période de planification et de tournées de véhicules pour nettoyer les débris (SRP-CD) après des catastrophes majeures. Le problème comprend des décisions stratégiques (planification) et opérationnelles (tournées) et prend en compte des questions complexes telles que deux niveaux de synchronisation : entre les équipes de travail et les camions-bennes, et entre les camions-bennes nécessaires pour charger, transporter et décharger les débris pendant les journées de travail. L'objectif du SRP-CD est double : minimiser le nombre de jours pour le nettoyage global, au niveau stratégique, et minimiser le coût total de routage des véhicules, au niveau opérationnel. Un nouveau modèle mathématique basé sur une formulation dynamique multi-flot, des heuristiques constructives, des métaheuristiques basées sur la recherche par grand voisinage (LNS) et des métaheuristiques hybrides basées sur la LNS et le recuit simulé sont proposés. Des expérimentations pour le modèle et les approches sont réalisées, afin de mesurer la performance et la robustesse des méthodes proposées. A notre connaissance, ce sont les premières contributions dans la littérature pour le SRP-CD, incluant tous les aspects abordés dans cette thèse.

Truckload transportation is a common mode of freight transportation, which accounts for a substantial portion of transportation industry, where shippers procure transportation services from carriers. Transportation service procurement is often realized by auction. Through designing effective auction mechanisms and efficient methods for solving related bid generation problems, shippers and carriers can save costs and increase profits respectively. This thesis studies three problems raised in the procurement of truckload transportation services realized by combinatorial auctions. Firstly, two two-phase combinatorial auction mechanisms are designed with supplementary bundles of requests offered for bid generated by the auctioneer and the carriers respectively in the second phase. Secondly, a column generation algorithm is proposed to solve the bid generation problem appeared in the combinatorial auction. Finally, the bid generation problem is extended to one that considers both multiple periods and uncertainty in truckload transportation service procurement. This stochastic optimization problem is formulated through scenario optimization and deterministic equivalence. To solve this model, a Benders decomposition approach is proposed.; Le transport par camions entiers est un mode courant de transport de marchandises, qui représente une part importante de l’industrie de transport, où les expéditeurs achètent des services de transport auprès des transporteurs. L'achat de services de transport est souvent réalisé par des enchères. Par concevoir des mécanismes d'enchères efficaces et des méthodes efficaces pour résoudre les problèmes de génération d'enchères associés, les expéditeurs et les transporteurs peuvent réduire leurs coûts et augmenter leurs bénéfices respectivement. Cette thèse étudie trois problèmes soulevés dans l'achat de services de transport par camions entiers réalisé par une enchère combinatoire. Premièrement, deux mécanismes d'enchères combinatoires à deux phases sont conçus avec des paquets supplémentaires de demandes offerts à l’enchère générés respectivement par le commissaire-priseur et les transporteurs dans la deuxième phase. Deuxièmement, un algorithme de génération de colonnes est proposé pour résoudre le problème de génération d'enchères apparu dans l'enchère combinatoire. Enfin, le problème de génération d’enchères est étendu à un problème qui tient compte à la fois plusieurs périodes et l'incertitude dans l'achat de services de transport par camions entières. Ce problème d'optimisation stochastique est formulé par l’optimisation de scénario et l’équivalence déterministe. Pour résoudre ce modèle, une approche de décomposition de Benders est proposée.

We study the value of information in semi-online single machine scheduling problems. We propose semi-online algorithms to solve these problems and evaluate their performances. Unlike the classical offline scheduling problems where the decision maker knows all characteristics of the instance to be scheduled, in online scheduling problems the decision-making is performed without previous information or only with partial information about the instance. Our work consists in distinguishing information that can improve the decision-making in a semi-online scheduling context from information that, even if available, does not bring any improvement. We mainly deal with semi-online problems for minimising the total completion time on a single machine. We start by studying several semi-online models with partial information on processing times of jobs. Then, we consider the problem with information on jobs release dates and finally the combination of information on processing times and jobs release dates. For each studied problem where partial information is identified as useful, we propose a semi-online algorithm integrating the information into the decision-making. We then evaluate its performance using a competitive analysis or a comparative experimental study.; Nous étudions la valeur de l’information dans des problèmes d’ordonnancement semi-online sur machine unitaire. Nous proposons ainsi des algorithmes semi-online pour résoudre ces problèmes et nous évaluons leurs performances. Contrairement aux problèmes d’ordonnancement classiques offline où le décideur connaît toutes les caractéristiques de l’instance à ordonnancer, dans les problèmes d’ordonnancement online ou semi-online la prise de décision est effectuée sans aucune information ou uniquement avec des informations partielles sur l’instance. Notre travail consiste à distinguer les informations qui peuvent améliorer la prise de décision dans un contexte d’ordonnancement semi-online des informations qui, même disponibles, n’apportent aucune amélioration. Nous traitons principalement les problèmes semi-online dont la fonction objective est la minimisation de la somme des dates de fin des tâches sur machine unitaire. Nous commençons par étudier plusieurs modèles semi-online avec des informations partielles sur les temps de traitement des tâches. Ensuite, nous considérons le problème avec une information sur les dates d’arrivée et finalement la combinaison de l’information sur les temps de traitements et les dates d’arrivée des tâches. Pour chaque problème étudié où l’information partielle est identifiée comme utile, nous proposons un algorithme semi-online intégrant l’information dans la prise de décision. Ensuite, nous évaluons sa performance à l’aide d’une analyse de compétitivité ou par étude expérimentale comparative.

This thesis, presented in view of obtaining an accreditation to supervise research, describes the research work I carried out as an assistant professor at the Université Paris Saclay during the last ten years. This work deals with the development of mixed-integer linear programming approaches for difficult deterministic and stochastic combinatorial optimization problems, mainly coming from applications in manufacturing, supply chain management and telecommunication.Part I is devoted to the work carried out on lot-sizing problems. We first study an extension of the discrete lot-sizing and scheduling problem in which the setup costs are sequencedependent and propose a new family of multi-item multi-period valid inequalities to strengthen the mathematical formulation of this problem. We then consider an important aspect of production planning, namely the fact that it is based on input data which are relative to the near futureand, as a consequence, are not always perfectly known at the time when the production plan has to be built. We thus study several stochastic programming approaches for lot-sizing. The first proposed approach assumes a rather simplified setting for the decision process. It namely considers a single-stage decision process in which the whole production plan is built before any additional information on the stochastic demand realization becomes available and cannot be updated afterward as the demand unfolds over time. We formulate this stochastic problemas a joint chance-constrained program and propose a new approximate solution approach for this problem called the partial sample approximation approach. Then, in order to further improve the modeling of the actual decision process, we investigate a multi-stage stochastic programming approach which explicitly takes into account the fact that production decisions are usually not made once and for all but rather adjusted over time according to the actual realizations of the uncertain parameters. Our main contribution consists in the development of a new algorithm capable of providing good-quality solutions for large-size instances of the stochastic single-item uncapacitated lot-sizing problem. This algorithm combines a nested decomposition algorithm called the Stochastic Dual Dynamic integer Programming (SDDiP) algorithm with a cutting-plane generation approach based on known valid inequalities. Finally, in order to extend the previous work which focuses on single-item single-echelon single-resource production systems, we consider a multi-item multi-echelon multi-resource production system linked to the remanufacturing of used products and study a multi-stage stochastic programming model for this problem. We thus present a customized branch-and-cut algorithm basedon a new family of valid inequalities for this problem.In parallel to the above-mentioned work on lot-sizing, I studied among others two applied facility location problems through industrial collaborations. The corresponding work is reported in Part II of the manuscript. We first discuss a facility location problem linked to the design of the outbound logistics network of Renault. The main contribution of this work is related to the development of a tractable heuristic solution approach for this complex large-size location-routing problem. We also investigate the placement of virtual network functions in a telecommunication network to secure it against a distributed denial-of-service attack. The main novelty here consists in the development of a new robust optimization model and adversarial algorithm for this problem.

In order to qualify quantum algorithms for industrial NP-Hard problems, comparing them to available polynomial approximate classical algorithms and not only to exact exponential ones is necessary. This is a great challenge as, in many cases, bounds on the reachable approximation ratios exist according to some highly-trusted conjectures of Complexity Theory. An interesting setup for such qualification is thus to focus on particular instances of these problems known to be “less difficult” than the worst-case ones and for which the above bounds can be outperformed: quantum algorithms should perform at least as well as the conventional approximate ones on these instances, up to very large sizes. We present a case study of such a protocol for two industrial problems drawn from the strongly developing field of smart-charging of electric vehicles. Tailored implementations of the Quantum Approximate Optimization Algorithm (QAOA) have been developed for both problems, and tested numerically with classical resources either by emulation of Pasqal’s Rydberg atom based quantum device or using Atos Quantum Learning Machine. In both cases, quantum algorithms exhibit the same approximation ratios as conventional approximation algorithms or improve them. These are very encouraging results, although still for instances of limited size as allowed by studies on classical computing resources. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.

Operating rooms are bottleneck resources for the flow of surgical patients and represent the main costs hub in acute care hospitals. Operating room planning and scheduling methods need to meet requirements of economic and operational efficiency as well as those of surgery safety. This thesis focuses on operating room scheduling under material and human resource constraints.Three decision levels are considered. Policies including bed management for the patients to surgery dates assignment and emergencies admission are evaluated by means of discrete event simulation and by considering resource shortages and wait times minimization objectives. The weekly scheduling of surgery is performed in two stages. A branch-and-price-and-cut algorithm is applied to schedule surgeries for a set of operating rooms under surgeon and nurse capacity constraints, surgery durations are deterministic. The second stage problem performs the nurse to surgery assignment considering objectives of nurse constant training, overtime minimization, visited operating rooms and by considering uncertain surgery duration. Finally, the insertion of emergency surgeries considering waiting time targets into given schedules of elective surgery is optimized by means of stochastic optimization techniques of queues systems. Developed problem solution methods are tested by means of numerical experiments and using real-world data from hospitals., Le bloc opératoire représente une ressource critique de l'activité chirurgicale et constitue un goulot d'étranglement pour le flux des patients ainsi que le principal générateur de coût des établissements hospitaliers. Les outils d'aide à la planification de l'activité chirurgicale doivent être à la hauteur des enjeux en termes d'efficience économique, opérationnelle et de qualité des soins. Dans cette thèse, on aborde des problématiques connexes de planification du bloc opératoire en focalisant l'attention sur la programmation des procédures chirurgicales sous contraintes des ressources matérielles et humaines.Trois niveaux de décisions sont traités. Les stratégies de planification des jours d'intervention sont optimisées en s'appuyant sur un modèle à simulation à événements discrets qui permet de jouer sur la projection des places disponibles en amont et en val du bloc, avec les critères d'améliorer les délais d'attente et l'insertion des urgences. La planification hebdomadaire se fait en deux étapes. Un algorithme de branch-and-price-and-cut planifie les chirurgies dans les salles sous des contraintes capacitaires de ressources infirmières et en considérant des durées opératoires déterministes. Une deuxième étape affecte le personnel infirmier avec des critères plus fins de rotation de l'activité et des dépassements horaires, en tenant compte de l'incertitude des durées opératoires. Enfin, l'insertion des urgences en cours de journée est étudiée par l'optimisation d'un système dynamique stochastique de file d'attente avec plusieurs délais d'urgence. Les méthodes sont validées par des expérimentations numériques utilisant des données hospitalières réelles.

Esta tesis está dedicada a un estudio en profundidad del Problema de Tarificación basado en Preferencias (del inglés, Rank Pricing Problem (RPP)) y dos generalizaciones. El RPP es un problema de optimización combinatoria que tiene como objetivo fijar el precio de los productos de una compañía para maximizar su beneficio. En él, intervienen clientes unit-demand, es decir, clientes que están interesados en varios de los productos de la empresa, pero pretenden comprar como mucho uno de ellos. Los clientes tienen un presupuesto fijo y clasifican los productos que les interesan formando un ranking del “mejor” al “peor”. Cuando la compañía fije los precios, cada cliente comprará su producto preferido de entre los que se puede permitir. En el RPP, asumimos que los productos se ofertan en cantidad ilimitada, lo cual encaja si consideramos que la compañía tiene suficientes productos para satisfacer la demanda, o cuando los productos se pueden producir rápidamente con un coste despreciable (por ejemplo, los bienes digitales). Esta tesis doctoral consta de cuatro capítulos. El primero de ellos es un capítulo de introducción al problema y a los conceptos matemáticos presentes en la tesis, mientras que los tres siguientes se centran en cada uno de los problemas estudiados: el RPP y dos generalizaciones. Así, el tercer capítulo está dedicado al estudio del Problema de Tarificación basado en Preferencias con Empates (RPPT por sus siglas en inglés, Rank Pricing Problem with Ties). En esta extensión del problema, asumimos que los clientes pueden expresar su indiferencia entre productos de su interés mediante empates en su lista de preferencia. Y el último capítulo de la tesis comprende el estudio del Problema de Tarificación Capacitado basado en Preferencias o Capacitated Rank Pricing Problem (CRPP) con envidia. En esta extensión, hemos asumido precios de reserva en los clientes que reflejan lo que están dispuestos a pagar por cada producto, en vez de un solo presupuesto por consumidor. No obstante, la principal diferencia es que en el CRPP la compañía tiene un número limitado de productos y puede no ser capaz de satisfacer la demanda de todos los clientes. El objetivo de la tesis es obtener formulaciones lineales enteras mixtas para los tres problemas estudiados, y compararlas teórica y/o computacionalmente. Para ello, la metodología empleada se basa en la propuesta de variables de decisión y restricciones apropiadas que modelicen el problema. El siguiente objetivo es la mejora de estas formulaciones mediante desigualdades válidas que reducen la región factible de la relajación del problema y permiten obtener una mejor cota de la relajación lineal. Y finalmente, un tercer objetivo es la propuesta de algoritmos de resolución para cada uno de estos modelos, y su posterior comparativa mediante la realización de estudios computacionales y resolución mediante optimizadores comerciales. En el Capítulo 2 introducimos dos formulaciones no lineales para el RPP, una que surge de una formulación binivel y otra que está formulada directamente en un solo nivel. Las comparamos teóricamente, linealizamos su función objetivo (que es la misma en ambos casos) de dos formas distintas y proponemos técnicas de preprocesamiento que reducen el tamaño de las instancias fijando variables binarias a cero o a uno. También estudiamos el problema de empaquetamiento asociado a las variables binarias del mejor modelo, con lo que probamos que esta formulación es muy fuerte porque la mayoría de las restricciones que contiene definen facetas del subproblema asociado. Los resultados computacionales son consistentes con nuestra comparación teórica, ya que muestran la superioridad del modelo uninivel. También revelan que se obtienen mejores cotas y un mejor rendimiento en general con una de las linealizaciones propuestas, que se emplea en capítulos posteriores. En el Capítulo 3, proponemos la primera formulación con variables de tres índices para el RPPT. Luego incluimos un método de resolución basado en la introducción de un modelo más débil con un conjunto de variables y restricciones de menor tamaño (el modelo de dos índices), formulación que a continuación fortalecemos añadiendo desigualdades válidas. El segundo método de resolución propuesto está basado en la descomposición de Benders, un método ampliamente utilizado para problemas enteros mixtos. Así, proponemos un Modelo de Benders válido con un conjunto de variables y restricciones pequeño, que reforzamos mediante desigualdades válidas que surgen de la resolución de los subproblemas de Benders. En los experimentos computacionales, observamos que cada uno de los algoritmos de resolución propuestos destaca en una fase de la resolución del problema. En la fase de la relajación lineal, resulta más rápida la adición de cortes en el modelo de dos índices, ya que las desigualdades se pueden separar por productos (incluso si se incluyen más cortes). En la fase entera, sin embargo, el Modelo de Benders lleva a cabo la exploración de nodos más rápido que el otro modelo, probablemente debido a su reducido número de variables y restricciones. El Capítulo 4 comienza introduciendo una formulación con variables de tres índices para resolver el CRPP. Al contrario que en los capítulos precedentes, en este se incluyen varios conjuntos de desigualdades válidas para dicha formulación que utilizan las restricciones de capacidad y nuevas variables binarias. Estos conjuntos se utilizan después cuando se proyecta el modelo de tres índices en el modelo de dos índices, por lo que las desigualdades obtenidas son más difíciles de separar porque dependen de seis conjuntos de parámetros. Además de resolver el problema de separación con Xpress, también separamos teóricamente un conjunto de desigualdades que resulta muy efectivo en la práctica, y lo relacionamos con un conjunto de cortes propuesto para el RPP. La combinación de estas desigualdades con las últimas que proponemos da como resultado un algoritmo muy eficiente que reúne las ventajas de ambas: proporciona unas de las mejores cotas de la relajación lineal y las fases de inclusión de cortes en el nodo raíz y de ramificación son muy rápidas This doctorate is entirely devoted to an in-depth study of the Rank Pricing Problem (RPP) and two generalizations. The RPP is a combinatorial optimization problem which aims at setting the prices of a series of products of a company to maximize its revenue. This problem is specified by a set of unit-demand customers, that is, customers interested in a subset of the products offered by the company which intend to buy at most one of them. To do so, they count on a fixed budget, and they rank the products of their interest from the “best” to the “worst”. Once the prices are established by the company, they will purchase their highest-ranked product among the ones they can afford. In the RPP, it is assumed an unlimited supply of products, which is consistent with a company having enough copies of a product to satisfy the demand, or with a setting where the products can be produced quickly at negligible cost (e.g., digital goods). This dissertation consists of four chapters. The first chapter introduces the RPP problem and the mathematical concepts present in the work, whereas each of the next three chapters tackles the resolution of each of the problems of study: the RPP and two generalizations. Thus, Chapter 3 is dedicated to the Rank Pricing Problem with Ties (RPPT), an extension of the RPP where we consider that customers can express indifference among products in their preference list. And the last chapter of the thesis is devoted to a generalization of the problem that we have named the Capacitated Rank Pricing Problem (CRPP) with envy. For this generalization, we have considered reservation prices of customers for the different products that reflect their willingness to pay, instead of a single budget per customer. However, the main difference is that, in the CRPP, the company has a limited supply of products and might not be able to satisfy all the customers’ requests. This is a realistic assumption that we can find in many companies. The aim of this thesis is the proposal of mixed-integer linear formulations for the three problems of study, and their theoretical and/or computational comparison. The methodology used is based on the introduction of decision variables and adequate restrictions to model the problems. Another objective consists in strengthening the formulations by means of valid inequalities that reduce the feasible region of the relaxed problem and allow us to obtain better linear relaxation bounds. Finally, a third goal is to derive resolution algorithms for each of these models and compare them computationally, using commercial solvers. In Chapter 2, we give two nonlinear formulations for the RPP, one that comes from a bilevel formulation and another one that is directly formulated as a single-level one. We compare them theoretically, linearize their objective functions (which are the same) in two different ways and propose preprocessing techniques that effectively reduce the size of the instances by fixing variables to either zero or one. By studying the Set Packing Problem associated to the binary variables of the strongest model, we prove that this formulation is very tight, since most of its constraints are facet-defining in the corresponding subproblem. The computational results are consistent with our theoretical comparison, given that they show the superiority of the single-level model. They also disclose that one of the linearizations (used in following chapters) outperforms the other. In Chapter 3, we propose the first formulation with three-index variables for the RPPT. Next, we propose a resolution method based on the introduction of a weaker model with much less variables and constraints (the two-index model) and its strengthening by means of valid inequalities. The second resolution method is based on the Benders decomposition, a widely used approach for solving mixed-integer programs. Thus, we introduce a valid Benders Model with a small number of variables and constraints. Next, we reinforce the model dynamically adding valid inequalities obtained solving the Benders subproblems. In the computational testing, each of the resolution algorithms proposed excels in a specific phase. In the linear relaxation phase, the separation procedure designed to add valid inequalities is faster for the two-index model, since these inequalities can be separated by products. In the integer phase, however, the Benders Model outperforms the two-index model in the tree search because the node exploration is faster, probably due to the small number of variables and constraints it has. Chapter 4 begins with the introduction of a model with three-index variables for the CRPP. Unlike in the previous chapters, here the capacity constraints and the inclusion of new variables associated to the capacity allow to derive several sets of valid inequalities for the three-index formulation. These sets are then included in the projection of the three-index formulation into the two-index one, so the resultant inequalities are more difficult to separate because they depend on six sets of parameters. Besides solving the separation problem with Xpress, we theoretically separate a particular set of inequalities that proves to be very effective in practice, and link it with a family proposed for the RPP. The combination of these inequalities with the last set proposed results in a very efficient resolution method that combines the best linear relaxation gap with a rather quick inclusion of cuts in the root node and an effective node search.

A complex system is a collection of subsystems which are independent enough to be distinguished but linked together in significant ways. This thesis considers the optimization of complex systems within the framework of multiobjective optimization and focuses on a representation of complex systems as coupled systems, meaning that the interaction between subsystems is modeled by coupling constraints, i.e. constraints involving variables from different subsystems.After having recalled the basic notions of multiobjective optimization and of dominance filtering algorithms, we introduce coupled problems, and define the key concept of decomposition in the multiobjective case. A simple implementation of decomposition already yields performance improvement in the resolution of uncoupled problems, but we provide further algorithmic improvements to the combination of solutions from subproblems and the elimination of dominated combinations, using notions of bounding boxes and of unidirectional dominance filtering algorithms.Beyond the uncoupled case, the main challenge of complex systems optimization remains to take coupling constraints into account, while never having to consider whole complex system optimization problem at once. We propose generic restrictions and relaxations of coupling constraints, which yield upper and lower bounds set on the set non-dominated set of a coupled problem. We show that bound sets can be obtained using decomposition.Finally, we present an application problem: a multiobjective multilocation assignment problem. We show that it admits a dynamic programming resolution method, and we show how decomposition can be used to improve on this initial resolution method. On the one hand, the sequential decision process can itself be broken down into independent subsequences. On the other hand, reasoning using bounds or bound sets obtained by decomposition can be used to speed up the sequential decision process by eliminating partial solutions early., Un système complexe peut être vu comme une collection de sous-systèmes irréductiblement liés mais assez indépendants pour être distingués. Cette thèse considère l'optimisation de systèmes complexes dans le cadre multi-objectifs. L'interaction entre sous-systèmes d'un système complexe y prend la forme de contraints couplantes, c’est-à-dire faisant intervenir des variables issues de différents sous-systèmes.Après avoir rappelé les fondements de l'optimisation multi-objectifs et de l’algorithmique de filtrage par dominance, nous présentons la notion de système couplé, et définissons dans le cas multi-objectifs celle, centrale, de décomposition. Une implémentation simple de la décomposition suffit à améliorer le temps de résolution de problèmes non-couplés. Nous proposons de surcroit des méthodes algorithmiques avancées pour la combinaison de solutions de sous-problèmes et l'élimination des combinaison dominées, utilisant les notions de boîte bornante et d’algorithme unidirectionnel de filtrage par dominance.Le défi principal de l'optimisation de systèmes complexes reste de prendre en compte les contraintes couplantes, tout en évitant de considérer l'entièreté du problème original en même temps. Nous proposons des restrictions et relaxations génériques des contraintes couplantes de problèmes couplés, permettant d'obtenir des ensembles bornant supérieurement et inférieurement l'ensemble de solutions non-dominées. Nous montrons que ceux-ci peuvent être calculés en tirant parti de la décomposition.Enfin, nous présentons un problème d’application : une affectation multi-site multi-objectifs sous contraintes de ressources. Nous montrons que ce problème admet un algorithme de résolution par la programmation dynamique, et comment la décomposition peut être utilisée pour améliorer cette méthode initiale. D’une part, le processus séquentiel de décision peut lui-même être décomposé en sous-séquences indépendantes. D’autre part, des bornes ou des ensembles bornant obtenus par décomposition peuvent être utilisés pour accélérer le processus séquentiel de décision par l’élimination précoce de solutions partielles.

Dans de nombreuses applications qui présentent un problème de décision ou d'optimisation combinatoire, il est utile de raisonner à différents niveaux d'abstraction. C'est tout d'abord le cas pour des missions d'exploration multi-robots, où l'on peut s'intéresser premièrement à la répartition de tâches d'exploration entre différents robots, puis à la manière dont chaque robot enchaîne les tâches qui lui sont allouées, et enfin à la décomposition de ces enchaînements de tâches sous la forme de déplacements à coordonner pour éviter des collisions ou pour maintenir des liens de communication. C'est aussi le cas pour la gestion d'une constellation de satellites d'observation de la Terre, pour lesquels on peut décider dans un premier temps de la répartition des tâches d'acquisition candidates entre les différents satellites, puis de l'enchaînement de ces acquisitions pour chaque satellite de la constellation, et enfin des commandes élémentaires à envoyer aux instruments pour réaliser effectivement cet enchaînement. C'est encore le cas pour l'implémentation de fonctions sur une architecture avionique, avec en premier lieu une décision concernant l'allocation de fonctions sur des unités de calcul temps réel, puis une décision concernant l'ordonnancement des fonctions sur chaque unité de calcul, et enfin une décision sur la stratégie de routage des données échangées entre fonctions sur un réseau disponible. D'un point de vue général, il est ainsi nécessaire dans ce type d'applications de considérer différents niveaux de décision couvrant allocation des tâches sur des ressources et ordonnancement des tâches sur ces mêmes ressources. Chaque tâche à considérer peut de plus se décomposer en plusieurs sous-tâches, dans le sens par exemple où une tâche de calcul d'une fonction correspond à l'enchaînement d'une tâche de lecture des données utilisées par la fonction, d'une tâche de calcul proprement dite, et d'une tâche d'écriture des sorties de la fonction dans une zone mémoire donnée. En plus de cela, les contraintes des problèmes de décision à résoudre peuvent être représentées avec différents niveaux d'abstraction. Par exemple, en exploration multi-robots, il existe des contraintes portant sur l'énergie disponible pour les robots. Au moment de la répartition des tâches d'exploration entre les robots, il n'est pas forcément possible pour des considérations combinatoires de considérer un modèle dynamique complexe reliant l'énergie disponible à la puissance consommée à chaque instant. On considère alors une consommation d'énergie forfaitaire pour chaque activité et une capacité maximale pour chaque robot. Le modèle d'énergie complexe peut être pris en compte dès lors que les tâches ont été réparties et que l'on synthétise les déplacements des robots. De manière analogue, pour l'agencement des observations d'un satellite, on peut considérer en première approximation qu'il existe une durée forfaitaire requise pour passer d'une observation à la suivante, avant de considérer des modèles cinématiques plus complexes prenant en compte les capacités des actionneurs gyroscopiques et les caractéristiques des zones à imager. Ce sujet de thèse s'intéresse à la définition de modèles et d'algorithmes de décision utilisables pour gérer ces problématiques de décision hiérarchique. In many decision making problems encountered in practice, there is a need to reason at different abstraction levels. This is the case for multi-robot exploration missions, which involve decisions on how exploration tasks are shared between robots, on how these tasks are successively realized by each robot, and on how robots moves are coordinated so as to avoid collisions or to maintain communication links. This is also the case for the management of a constellation of Earth observation satellites, for which decisions must be made concerning how candidate observation tasks are shared between satellites, concerning how each satellite realizes the set of observation tasks allocated to it, and concerning the basic commands that must be sent to instruments for achieving the acquisition plan. This is again the case for the mapping of functions onto an embedded architecture, with first a decision concerning the allocation of functions onto real-time computation units, then a decision concerning the scheduling of functions on each unit, and last a decision on the routing of data exchanged between functions inside an available inter-units network. From a general point of view, such applications require being able to deal with different decision levels covering task allocation and task scheduling over ressources. Additionnally, each task involved must also sometimes be decomposed into subtasks, as in the case of a function computation task which is decomposed into one subtask for reading the set of data used by the function, one subtask for actually performing the computation, and one subtask for writing the result of the computation in a dedicated buffer. Additionnally, the constraints of the decision making problem to solve can be modeled using different abstraction levels. For instance, in multi-robot exploration, there exist constraints on the energy available for each robot all along the mission. At the time of task sharing between robots, it is not possible for combinatorial reasons to consider a complex dynamic model linking the level of energy available to the instantaneous power consumption. Instead, a simpler model might be used, in which a fixed amount of energy is consumed by each task. The complex energy model can be considered again once tasks have been allocated to robots and once robot moves have been synthesized. Similarly, for Earth observing satellites, it is possible to consider a fixed duration between the realization of two successive activities before considering finer a model taking into account the kinematics of satellites and the coordinates of images to be realized. The goal of this thesis is to define new models and algorithms for handling such hierarchical decision making problems.

Over-parameterized networks, where the number of parameters surpass the number of train-ing samples, generalize well on various tasks. However, large networks are computationally expensive in terms of the training and inference time. Furthermore, the lottery ticket hy-pothesis states that a subnetwork of a randomly initialized network can achieve marginal loss after training on a specific task compared to the original network. Therefore, there is a need to optimize the inference and training time, and a potential for more compact neural architectures. We introduce a novel approach “Optimizing ANN Architectures using Mixed-Integer Programming” (OAMIP) to find these subnetworks by identifying critical neurons and re-moving non-critical ones, resulting in a faster inference time. The proposed OAMIP utilizes a Mixed-Integer Program (MIP) for assigning importance scores to each neuron in deep neural network architectures. Our MIP is guided by the impact on the main learning task of the net-work when simultaneously pruning subsets of neurons. In concrete, the optimization of the objective function drives the solver to minimize the number of neurons, to limit the network to critical neurons, i.e., with high importance score, that need to be kept for maintaining the overall accuracy of the trained neural network. Further, the proposed formulation generalizes the recently considered lottery ticket hypothesis by identifying multiple “lucky” subnetworks, resulting in optimized architectures, that not only perform well on a single dataset, but also generalize across multiple ones upon retraining of network weights. Finally, we present a scalable implementation of our method by decoupling the importance scores across layers using auxiliary networks and across di˙erent classes. We demonstrate the ability of OAMIP to prune neural networks with marginal loss in accuracy and generalizability on popular datasets and architectures., Les réseaux sur-paramétrés, où le nombre de paramètres dépasse le nombre de données, se généralisent bien sur diverses tâches. Cependant, les grands réseaux sont coûteux en termes d’entraînement et de temps d’inférence. De plus, l’hypothèse du billet de loterie indique qu’un sous-réseau d’un réseau initialisé de façon aléatoire peut atteindre une perte marginale après l’entrainement sur une tâche spécifique par rapport au réseau de référence. Par conséquent, il est nécessaire d’optimiser le temps d’inférence et d’entrainement, ce qui est possible pour des architectures neurales plus compactes. Nous introduisons une nouvelle approche “Optimizing ANN Architectures using Mixed-Integer Programming” (OAMIP) pour trouver ces sous-réseaux en identifiant les neurones importants et en supprimant les neurones non importants, ce qui permet d’accélérer le temps d’inférence. L’approche OAMIP proposée fait appel à un programme mixte en nombres entiers (MIP) pour attribuer des scores d’importance à chaque neurone dans les architectures de modèles profonds. Notre MIP est guidé par l’impact sur la principale tâche d’apprentissage du réseau en élaguant simultanément les neurones. En définissant soigneusement la fonction objective du MIP, le solveur aura une tendance à minimiser le nombre de neurones, à limiter le réseau aux neurones critiques, c’est-à-dire avec un score d’importance élevé, qui doivent être conservés pour maintenir la précision globale du réseau neuronal formé. De plus, la formulation proposée généralise l’hypothèse des billets de loterie récemment envisagée en identifiant de multiples sous-réseaux “chanceux”. Cela permet d’obtenir des architectures optimisées qui non seulement fonctionnent bien sur un seul ensemble de données, mais aussi se généralisent sur des di˙érents ensembles de données lors du recyclage des poids des réseaux. Enfin, nous présentons une implémentation évolutive de notre méthode en découplant les scores d’importance entre les couches à l’aide de réseaux auxiliaires et entre les di˙érentes classes. Nous démontrons la capacité de notre formulation à élaguer les réseaux de neurones avec une perte marginale de précision et de généralisabilité sur des ensembles de données et des architectures populaires.

Évaluer la vulnérabilité des réseaux est un enjeu de plus en plus critique. Dans ce mémoire, nous nous penchons sur une approche étudiant la défense d’infrastructures stratégiques contre des attaques malveillantes au travers de problèmes d'optimisations multiniveaux. Plus particulièrement, nous analysons un jeu séquentiel en trois étapes appelé le « Multilevel Critical Node problem » (MCN). Ce jeu voit deux joueurs s'opposer sur un graphe: un attaquant et un défenseur. Le défenseur commence par empêcher préventivement que certains nœuds soient attaqués durant une phase de vaccination. Ensuite, l’attaquant infecte un sous ensemble des nœuds non vaccinés. Finalement, le défenseur réagit avec une stratégie de protection. Dans ce mémoire, nous fournissons les premiers résultats de complexité pour MCN ainsi que ceux de ses sous-jeux. De plus, en considérant les différents cas de graphes unitaires, pondérés ou orientés, nous clarifions la manière dont la complexité de ces problèmes varie. Nos résultats contribuent à élargir les familles de problèmes connus pour être complets pour les classes NP, $\Sigma_2^p$ et $\Sigma_3^p$. Motivés par l’insolubilité intrinsèque de MCN, nous concevons ensuite une heuristique efficace pour le jeu. Nous nous appuyons sur les approches récentes cherchant à apprendre des heuristiques pour des problèmes d’optimisation combinatoire en utilisant l’apprentissage par renforcement et les réseaux de neurones graphiques. Contrairement aux précédents travaux, nous nous intéressons aux situations dans lesquelles de multiples joueurs prennent des décisions de manière séquentielle. En les inscrivant au sein du formalisme d’apprentissage multiagent, nous concevons un algorithme apprenant à résoudre des problèmes d’optimisation combinatoire multiniveaux budgétés opposant deux joueurs dans un jeu à somme nulle sur un graphe. Notre méthode est basée sur un simple curriculum : si un agent sait estimer la valeur d’une instance du problème ayant un budget au plus B, alors résoudre une instance avec budget B+1 peut être fait en temps polynomial quelque soit la direction d’optimisation en regardant la valeur de tous les prochains états possibles. Ainsi, dans une approche ascendante, nous entraînons notre agent sur des jeux de données d’instances résolues heuristiquement avec des budgets de plus en plus grands. Nous rapportons des résultats quasi optimaux sur des graphes de tailles au plus 100 et un temps de résolution divisé par 185 en moyenne comparé au meilleur solutionneur exact pour le MCN., Evaluating the vulnerability of networks is a problem which has gain momentum in recent decades. In this work, we focus on a Multilevel Programming approach to study the defense of critical infrastructures against malicious attacks. We analyze a three-stage sequential game played in a graph called the Multilevel Critical Node problem (MCN). This game sees two players competing with each other: a defender and an attacker. The defender starts by preventively interdicting nodes from being attacked during what is called a vaccination phase. Then, the attacker infects a subset of non-vaccinated nodes and, finally, the defender reacts with a protection strategy. We provide the first computational complexity results associated with MCN and its subgames. Moreover, by considering unitary, weighted, undirected and directed graphs, we clarify how the theoretical tractability or intractability of those problems vary. Our findings contribute with new NP-complete, $\Sigma_2^p$-complete and $\Sigma_3^p$-complete problems. Motivated by the intrinsic intractability of the MCN, we then design efficient heuristics for the game by building upon the recent approaches seeking to learn heuristics for combinatorial optimization problems through graph neural networks and reinforcement learning. But contrary to previous work, we tackle situations with multiple players taking decisions sequentially. By framing them in a multi-agent reinforcement learning setting, we devise a value-based method to learn to solve multilevel budgeted combinatorial problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to B, then solving instances with budget B+1 can be done in polynomial time regardless of the direction of the optimization by checking the value of every possible afterstate. Thus, in a bottom-up approach, we generate datasets of heuristically solved instances with increasingly larger budgets to train our agent. We report results close to optimality on graphs up to 100 nodes and a 185 x speedup on average compared to the quickest exact solver known for the MCN.

Scheduling problems are combinatorial optimization problems arising in project management: the aim is to schedule tasks execution under resource constraints or precedence constraints so as to minimize a cost or maximize a gain. An integer linear programm (ILP° consists in optimizing a linear objective function over the integer points satisfying linear constraints. A lot of operation research problems can be formulated as ILP, and then be solved by commercial ILP. This thesis focuses on a single machine scheduling problem where earliness and tardiness with respect to a common due date have to be minimized. Thanks to so-called dominance properties used in the scheduling field, we propose several ILP formulation for this problem. First formulations, which are based on continuous variables similar to completion times variables (natural variables), use non-overlapping inequalities. Last formulations, which are based on binary partition variables, rely on a new type of linear inequalities that translate dominance properties.; Les problèmes d’ordonnancement sont des problèmes d’optimisation combinatoire modélisant la gestion de projets: il s’agit de planifier l’exécution de tâches, sous des contraintes de ressources ou de précédence et de manière à minimiser un coût ou maximiser un gain. On appelle programmation linéaire en nombres entiers (PLNE) l’optimisation d’une fonction linéaire sur les points entiers vérifiant un lot de contraintes linéaires. Cet outil permet de modéliser de nombreux problèmes de recherche opérationnelle, qui peuvent alors être résolus par des solveurs implémentant l’algorithme du simplexe dans un schéma de branchement et évaluation. Cette thèse porte sur l’étude d’un problème d’ordonnancement où les tâches doivent être exécutées sur une machine de manière à minimiser les pénalités d’avance et de retard par rapport à une date de fin souhaitée commune. Grâce à des propriétés dites de dominance utilisées par la communauté de l’ordonnancement, nous avons fourni plusieurs formulations PLNE modélisant ce problème. Les premières formulations, basées sur des variables continues comparables à des dates de fin, dites variables naturelles, utilisent des inégalités de non-chevauchement. Les dernières formulations, basées sur des variables booléennes de partitions, reposent sur un type nouveau d’inégalités linéaires qui traduisant des propriétés de dominance.

Sequencing is a process in biology that determines the order of nucleotides in the DNA. It produces a set of fragments, called reads, in which the genetic information is known. Unfortunatly, the genomic sequence is decomposed in small pieces. In order to analyse it, it is necessary to reconstruct it using a number of computer processes. In this thesis, we studied two mathematical problems arising from this sequencing: the scaffolding and the linearization.The scaffolding is a process that takes place after the reads assembly into larger subsequences called contigs. It consists in the search of paths and cycles in a particular graph called scaffold graph. These paths and cycles represent the linear and circular chromosomes of the organism whose DNA has been sequenced. The linearization is a problem related to the scaffolding. When we take into account that contigs may appear several times in the genomic sequence, some ambiguities can arise. If this ambiguities are not deleted, then a chimeric sequence may be produced by the scaffolding. To solve this problem, a solution computed by the scaffolding should be wisely deteriorated. In any case, both problems can be modelized as optimization problems in a graph.In this document, we study both problems focusing on three aspects. The first aspect consists in the study of the complexity of these problems. The second aspect consists in the development of algorithms, exact or approximate, to solve these problems. Finally, the last aspect consists in implementing and testing these algorithms to look at their behaviors on real instances.; Le séquençage est un processus en biologie qui permet de déterminer l'ordre des nucléotides au sein de la molécule d'ADN. Le séquençage produit un ensemble de fragments, appelés lectures, dans lesquels l'information génétique est connue. Seulement, la séquence génomique n'est connue que de façon parcellaire, pour pouvoir faire son analyse, il convient alors de la reconstituer à l'aide d'un certain nombre de traitements informatiques. Dans cette thèse, nous avons étudié deux problèmes mathématiques issus de ce séquençage : l'échafaudage et la linéarisation.L'échafaudage est un processus qui intervient après l'assemblage des lectures en contigs. Il consiste en la recherche de chemins et de cycles dans un graphe particulier appelé graphe d'échafaudage. Ces chemins et cycles représentent les chromosomes linéaires et circulaires de l'organisme dont l'ADN a été séquencée. La linéarisation est un problème annexe à l'échafaudage : quand on prend en compte le fait que les contigs puissent apparaitre plusieurs fois dans la séquence génomique, des ambiguïtés surviennent dans le calcul d'une solution. Celles-ci, si elles ne sont pas traitées, peuvent entrainer la production d'une séquence chimérique lors de l'échafaudage. Pour résoudre ce problème, il convient alors de dégrader de façon parcimonieuse une solution calculée par l'échafaudage. Dans tous les cas, ces deux problèmes peuvent être modélisés comme des problèmes d'optimisation dans un graphe.Dans ce document, nous ferons l'étude de ces deux problèmes en se concentrant sur trois axes. Le premier axe consiste à classifier ces problèmes au sens de la complexité. Le deuxième axe porte sur le développement d'algorithmes, exacts ou approchés, pour résoudre ces problèmes. Enfin, le dernier axe consiste à implémenter et tester ces algorithmes pour observer leurs comportements sur des instances réelles.

Sequencing is a process in biology that determines the order of nucleotides in the DNA. It produces a set of fragments, called reads, in which the genetic information is known. Unfortunatly, the genomic sequence is decomposed in small pieces. In order to analyse it, it is necessary to reconstruct it using a number of computer processes. In this thesis, we studied two mathematical problems arising from this sequencing: the scaffolding and the linearization.The scaffolding is a process that takes place after the reads assembly into larger subsequences called contigs. It consists in the search of paths and cycles in a particular graph called scaffold graph. These paths and cycles represent the linear and circular chromosomes of the organism whose DNA has been sequenced. The linearization is a problem related to the scaffolding. When we take into account that contigs may appear several times in the genomic sequence, some ambiguities can arise. If this ambiguities are not deleted, then a chimeric sequence may be produced by the scaffolding. To solve this problem, a solution computed by the scaffolding should be wisely deteriorated. In any case, both problems can be modelized as optimization problems in a graph.In this document, we study both problems focusing on three aspects. The first aspect consists in the study of the complexity of these problems. The second aspect consists in the development of algorithms, exact or approximate, to solve these problems. Finally, the last aspect consists in implementing and testing these algorithms to look at their behaviors on real instances.; Le séquençage est un processus en biologie qui permet de déterminer l'ordre des nucléotides au sein de la molécule d'ADN. Le séquençage produit un ensemble de fragments, appelés lectures, dans lesquels l'information génétique est connue. Seulement, la séquence génomique n'est connue que de façon parcellaire, pour pouvoir faire son analyse, il convient alors de la reconstituer à l'aide d'un certain nombre de traitements informatiques. Dans cette thèse, nous avons étudié deux problèmes mathématiques issus de ce séquençage : l'échafaudage et la linéarisation.L'échafaudage est un processus qui intervient après l'assemblage des lectures en contigs. Il consiste en la recherche de chemins et de cycles dans un graphe particulier appelé graphe d'échafaudage. Ces chemins et cycles représentent les chromosomes linéaires et circulaires de l'organisme dont l'ADN a été séquencée. La linéarisation est un problème annexe à l'échafaudage : quand on prend en compte le fait que les contigs puissent apparaitre plusieurs fois dans la séquence génomique, des ambiguïtés surviennent dans le calcul d'une solution. Celles-ci, si elles ne sont pas traitées, peuvent entrainer la production d'une séquence chimérique lors de l'échafaudage. Pour résoudre ce problème, il convient alors de dégrader de façon parcimonieuse une solution calculée par l'échafaudage. Dans tous les cas, ces deux problèmes peuvent être modélisés comme des problèmes d'optimisation dans un graphe.Dans ce document, nous ferons l'étude de ces deux problèmes en se concentrant sur trois axes. Le premier axe consiste à classifier ces problèmes au sens de la complexité. Le deuxième axe porte sur le développement d'algorithmes, exacts ou approchés, pour résoudre ces problèmes. Enfin, le dernier axe consiste à implémenter et tester ces algorithmes pour observer leurs comportements sur des instances réelles.

The greedy approach is natural for the design of algorithms. It is fast, easy to implement, has a good performance on average, and is applicable to many optimization problems in various settings. For those reasons, it is an important heuristic in practice. In this thesis, we present greedy algorithms for three different NP-hard optimization problems. We discuss the relation between those algorithms, their proof techniques and the structure of the problems under study. In the first part of this thesis, we focus on the Maximum Coverage problem with a connectivity constraint, which comes up for the design of wireless networks. We show that the problem is NP-hard, even when the coverage and the connectivity are induced by a set of unit disks in the plane. For that special case, we show that greedily picking two disks so as to maximize the marginal area covered while correctness achieves a 2-approximation. We further improve the approximation ratio by providing a PTAS for this problem with a small resource augmentation, using Arora’s shifted grid dissection technique. In the second part of this thesis, we focus on the Maximum Independent Set problem. A natural approach is to repeatedly pick a vertex of minimum degree, and remove it and its neighbours from the graph. We present a new technique to analyze the performance of this greedy approach in various classes of graphs and address the following question: if there are several minimun-degree vertices, what vertex should the greedy algorithm pick in order to maximise the size of the final solution ? With this tool, we design an ”ultimate tie-breaking” rule that leads to the best possible approximation ratio for sub-cubic graphs and for this type of greedy algorithms. We complement this by lower bound results that show that designing good tie-breaking rules is a difficult task. The third and last part of the thesis is devoted to the Maximum Integral Multiflows problem. The problem is difficult and well-studied. For instance, a constant factor approximation is unlikely to exist even when the supply graph is planar and cubic. In the special case where the supply graph together with the demand edges form a bounded genus graph, we present a constant factor approximation algorithm. The algorithm consists of a succession of greedy procedures that exploit topological properties of graphs and curves on surfaces., L’approche gloutonne est naturelle pour concevoir un algorithme. Elle permet la conception d’algorithmes rapides, faciles à implémenter, qui produisent en moyenne des solutions de qualité, pour de nombreux problèmes d’optimisation. Pour ces raisons, c’est une heuristique importante en pratique. Dans cette thèse, nous présentons des algorithmes gloutons pour trois problèmes d’optimisation NP-difficiles. Nous discutons les relations entre ces algorithmes, leurs techniques de preuve et la structure des problèmes étudiés. Dans la première partie de cette thèse, on se concentre sur le problème de la couverture maximale avec une contrainte de connexité, contrainte que l’on rencontre lors de la conception de réseaux sans fil. Nous montrons que le problème est NP-difficile, même quand la couverture et la connexité proviennent d’un ensemble de disques unité dans le plan. Pour ce cas particulier, nous montrons que choisir de manière gloutonne deux disques qui maximisent le gain marginal tout en maintenant la solution connexe réalise une 2-approximation. Nous améliorons ce ratio d’approximation en donnant un schéma d’approximation en temps polynomial avec une légère augmentation de ressource, basé sur la technique d’Arora pour le voyageur de commerce euclidien. Dans la deuxième partie de cette thèse, on se concentre sur le problème du stable maximum. Une approche naturelle est de successivement choisir un sommet de degré minimum, le placer dans la solution en construction, puis le retirer avec ses voisins du graphe. Nous présentons une nouvelle technique pour analyser la performance de cette approche gloutonne dans différentes classes de graphes et abordons la question suivante : s’il y a plusieurs sommets de degré minimum, lequel l’algorithme devrait-il choisir pour maximiser la taille de la solution finale ? Avec cet outil, nous concevons une règle pour briser les cas d’égalité, qui conduit à la meilleure approximation possible dans les graphes sous-cubiques et pour ce type d’algorithmes gloutons. Nous complémentons ces résultats par des résultats négatifs qui suggèrent que la conception de bonnes règles brisant les cas d’égalité est une tâche difficile. La troisième et dernière partie de la thèse est consacrée au problème du multiflot entier maximum. Ce problème est difficile et a été très étudié. Par exemple, une approximation de facteur constant est probablement impossible même quand le graphe d’offre est planaire et cubique. Dans le cas particulier où le graphe d’offre et les arêtes de demande forment ensemble un graphe de genre borné, nous présentons un algorithme avec un facteur d’approximation constant. L’algorithme consiste en une succession de procédures gloutonnes qui exploitent les propriétés topologiques des graphes et des lacets sur des surfaces.

With the emergence of Smart Grid and communication technology between customer and supplier, there has been a growing interest in Demand Response research with different electricity pricing such as “Time-of-Use” (ToU), “Critical-Peak-Pricing”. As a response to these circumstances, we study a two-machine flow shop scheduling problem with minimization of total electricity cost (TEC) under ToU. We deal with two sub-problems. The first one tackles the joint optimization of makespan and TEC in a two-machine flow shop scheduling problem under ToU. We optimize TEC without increasing the makespan. The resolution approach is based on the theory of equivalent solutions of (F2 || Cmax) which is applied for the first time in the optimization of electricity costs. The second problem minimizes the TEC of a two machines flow shop scheduling problem with the consideration of several machine operating states under ToU. We develop a property based on Johnson’s rule to determine the optimal sequence for general ToU pricing structures. We design a new linear programming and an exact method based on the Benders decomposition to solve the problem. The numerical tests show that our proposed approach significantly improves the quality of existing results in the literature. The thesis builds a decision support tool for managers to reduce the cost of electricity in production and opens up new perspectives for energy optimization in industry.; Avec l’émergence du Smart Grid et des outils de communication entre clients et compagnies d’électricité, la réponse à la demande attire de plus en plus attentions avec des tarification d’électricité tels que « Time-of-Use » (ToU), « Critical-Peak-Pricing ». Dans ce contexte, nous menons une étude sur l’optimisation de coût d’électricité (TEC) dans le problème d’ordonnancement de flow shop à deux machines sous la tarification d’électricité ToU. Nous traitons deux sous problèmes. Le premier minimise le TEC de la solution optimale de (F2||Cmax). Nous construisons un plan de production de coût d’électricité minimal avec le makespan optimal. L’approche de résolution repose sur la théorie des solutions équivalentes de (F2||Cmax) qui sera appliquée pour la première fois dans l’optimisation de coût d’électricité. Le deuxième minimise le TEC de flow shop à deux machines avec la prise en compte de plusieurs états de fonctionnement de machines. Nous développons une proposition fondée sur la règle de Johnson pour déterminer la séquence optimale pour les structures générales de ToU. Nous concevons une nouvelle programmation linéaire et une méthode exacte fondée sur la décomposition de Benders pour résoudre le problème. Les tests numériques montrent que l’approche proposée améliore d’une manière significative la qualité des résultats existants dans la littérature. La thèse permet de construire un outil d’aide de décision au manager de réduire le coût d’électricité de production, d’ouvrir de nouvelles perspectives pour l’optimisation énergétique dans l’industrie.

Tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations research.In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions.; Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opérationnelle.Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/planning.Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente.Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues.

Tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations research.In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions.; Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opérationnelle.Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/planning.Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente.Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues.

Quantum machine provide an opportunity to revolutionizing many fields, especially in combinatorial algorithms. In this internship, we propose to assess the performance of existing (and published) algorithms and clarify the opportunities ofquantum algorithms. In a first step, we use a search algorithm on an unstructured database published by Lov Grover (1996) and two other algorithms inspired by the Grover algorithm dealing with the satisfiability problem on a logical formulas and search for elements in an array. The second part present quantum algorithms necessary to do combinatorial optimization, such as the sumation and minimization. Finally, we experimentally solve the problem of vertex cover and traveling salesman problem.; L’arrivée des machines quantiques risque de révolutionner de nombreux domaines, en particulier celui des algorithmes combinatoires. Nous proposons dans ce stage d’évaluer la performance des algorithmes existants (et publiés) et d’éclairerles opportunités des algorithmes quantiques. Dans un premier temps, nous allons aborder l’algorithme de recherche dans une base non structurée de Lov Grover (1996) ainsi que deux autres algorithmes inspirés de l’algorithme de Grover traitant le problème de satisfiabilité d’une formule logique et la recherche d’éléments dans un tableau. La seconde partie présente des algorithmes quantiques nécessaires pour faire de l’optimisation combinatoire, tels que la somme ou encore la minimisation. Enfin,nous abordons le problème de la couverture d’arêtes (Vertex Cover - VC) et voyageur de commerce (Traveling Salesman Problem - TSP).

Existing approaches for graph-based deep dependency parsing that force connexity in predicted graphs do no cover the structures observed in French treebanks. We propose a novel algorithm that covers the full set of possible structures. We evaluate our approach on the French corpora FTB and Sequoia and observe a trade-off between the validity of predicted structures and the quality of predictions; Les algorithmes existants pour l’analyse en dépendances profondes fondée sur les graphes capables de garantir la connexité des structures produites ne couvrent pas les corpus du français. Nous proposons un nouvel algorithme qui couvre l’ensemble des structures possibles. Nous nous évaluons sur les corpus français FTB et Sequoia et observons un compromis entre la production de structures valides et la qualité des analyses.

Network Functions Virtualization (NFV) and Software Defined Networking (SDN) are two promising techniques for the next generation of telecommunication networks. Their introduction allows time, energy, and cost minimization. In this dissertation, we study a problem faced by network service providers, named, the Virtual Network Functions Placement and Routing problem (VNFPRP) in Software Defined Networks.We start proving that the VNFPRP is NP-hard in a strong sense, even for a single commodity and without node-capacity, VNFs-capacity, latency, and precedence constraints. We provide a compact Mixed Integer Linear Programming (MILP) formulation to model it. This formulation does not seem to be strong enough for finding a solution using an off-the-shelf solver. In order to tackle the problem from a computational perspective, we provide MILP-based heuristic. The obtained results indicate that our MILP-heuristic provides high-quality solutions.Moreover, we propose two extended formulations for the problem and derive a Branch-and-Price algorithm. We also provide several families of valid inequalities to strengthen the LP-bounds. We present computational results and discuss the performance of each algorithm.Furthermore, we discuss a variant of the problem, and we provide theoretical results that allow us to derive Benders reformulation of the problem, along with several families of valid inequalities. These ingredients are combined in a Branch-and-Benders-Cut framework and computationally tested on a wide range of realistic instances and compared with the Automatic Benders decomposition provided by Cplex.Computational results indicate that our decomposition and reformulation approaches are more efficient compared to the two methods (the MILP compact formulation and the automatic Benders) provided by the off-the-shelf solver on a set of realistic instances, both in terms of CPU time and overall solution quality., La virtualisation des fonctions réseau et les réseaux définis par logiciel sont deux nouvelles technologies prometteuses qui émergent dans la nouvelle génération des réseaux de télécommunication. Leur introduction permet la minimisation du temps de traitement des services, et un gain en énergie et en coûts. Dans cette thèse, nous étudions un problème confronté par les fournisseurs des services réseau, intitulé le problème de placement des fonctions virtuelles et de routage des services dans les réseaux définis par logiciel. Nous commençons par prouver que le problème est NP-Difficile au sens fort, même en considérant une seule commodité, et en relâchant les contraintes de capacité sur les nœuds et sur les fonctions virtuelles, et aussi les contraintes de latence et de précédence. Nous proposons ensuite une formulation PLNE (Programmation linéaire en nombres entiers) compacte pour modéliser le problème. Cette formulation ne semble pas être assez séré pour trouver des solutions réalisables en un temps raisonnable à l'aide d'un solveur standard. Afin de remédier à cela, nous fournissons, une heuristique basée sur une formulation PLNE. Nous proposons également, deux formulations PLNE étendues pour modéliser le problème et nous définissons l'algorithme de Branch-and-Pricer associé. En plus, nous définissons plusieurs familles d'inégalités valides afin de renforcer la relaxation linéaire. Nous comparons les deux algorithmes proposés et nous discutons leur performance. Ensuite, nous étudions une variante du problème et nous présentons des résultats théoriques qui nous permettent de la reformuler en appliquant la décomposition de Benders. Nous renforçons cette reformulation par un ensemble d'inégalités valides. Tout cela est combiné dans algorithme de Branch-and-Benders-cut que nous avons testé et comparé avec l'algorithme de Benders automatique inclus dans le solveur commercial Cplex. Les résultats numériques indiquent que nos approches de décomposition et de reformulation sont plus efficaces par rapport aux deux méthodes (la formulation compacte et l'algorithme de Benders automatique) fournies par un solveur standard sur un ensemble d'instances réalistes, à la fois en terme de temps CPU et en terme de qualité de la solution. Les résultats indiquent également que notre heuristique fournit des solutions de haute qualité.

By connecting billions of things to the Internet, IoT created a plethora of applications that touch every aspect of human life. Time-sensitive, mission-critical services, require robust connectivity and strict reliability constraints. On the other hand, the IoT relies mainly on Low-power Lossy Networks, which are unreliable by nature due to their limited resources, hard duty cycles, dynamic topologies, and uncertain radio connectivity. Faults in LLNs are common rather than rare events, therefore, maintaining continuous availability of devices and reliability of communication, are critical factors to guarantee a constant, reliable flow of application data.After a comprehensive literature review, and up to our knowledge, it is clear that there is a call for a new approach to monitoring the unreliable nodes and links in an optimized, energy-efficient, proactive manner, and complete interoperability with IoT protocols. To target this research gap, our contributions address the correct assignment (placement) of the monitoring nodes. This problem is known as the minimum assignment problem, which is NP-hard. We target scalable monitoring by mapping the assignment problem into the well-studied MVC problem, also NP-hard. We proposed an algorithm to convert the DODAG into a nice-tree decomposition with its parameter (treewidth) restricted to the value one. As a result of these propositions, the monitor placement becomes only Fixed-Parameter Tractable, and can also be polynomial-time solvable.To prolong network longevity, the monitoring role should be distributed and balanced between the entire set of nodes. To that end, assuming periodical functioning, we propose in a second contribution to schedule between several subsets of nodes; each is covering the entire network. A three-phase centralized computation of the scheduling was proposed. The proposition decomposes the monitoring problem and maps it into three well-known sub-problems, for which approximation algorithms already exist in the literature. Thus, the computational complexity can be reduced.However, the one major limitation of the proposed three-phase decomposition is that it is not an exact solution. We provide the exact solution to the minimum monitor assignment problem with a duty-cycled monitoring approach, by formulating a Binary Integer Program (BIP). Experimentation is designed using network instances of different topologies and sizes. Results demonstrate the effectiveness of the proposed model in realizing full monitoring coverage with minimum energy consumption and communication overhead while balancing the monitoring role between nodes.The final contribution targeted the dynamic distributed monitoring placement and scheduling. The dynamic feature of the model ensures real-time adaptation of the monitoring schedule to the frequent instabilities of networks, and the distributed feature aims at reducing the communication overhead.; Les réseaux « Internet des Objets » se composent de plusieurs millions d’objets qui possèdent une adresse IP et qui peuvent connecter sur Internet. En général, ces objets sont supposé d’être autonomes et peuvent résoudre des tâches; mesurer, traiter et fournir des informations pour les systèmes connectés et pour les utilisateurs. Aussi, ces réseaux sont vulnérables (c.-à-d. : les éléments peuvent être mobiles et la topologie du réseau peut changer dynamiquement), les changements peuvent influencer le (bon) fonctionnement du réseau. De plus, ils peuvent être alimentés par des batteries de durée de vie limitée, ce que nécessite la réduction de leur consommation.Ce travail de thèse aborde un sujet important dans le domaine de l’Internet des Objets, qui consiste à savoir comment assurer la robustesse et le fonctionnement tolérant aux pannes du réseau pour répondre aux exigences des missions critiques. Avec le large déploiement des services IdO, ce problème est deventé ou de détection de pannes et de sécurité industriel où l’état des objets communicants doit être constamment vérifié pour le rétablissement rapide en cas de problème particulièrement crucial pour les applications telles que le monitorage intelligent de sames de communication inattendus. On cherche alors de minimiser le coût du monitorage et l’utilisation de l’énergie, et aussi les charges additionnelles sur les réseaux.Nous avons proposé un algorithme qui vise à réaliser un placement distribué des moniteurs avec une complexité minimale pour le calcul. L’algorithme proposé fonctionne avec RPL. L’objectif principal est d’augmenter la robustesse dans les réseaux IdO ciblant les applications critiques en temps réel via le monitorage des liaisons dans les DODAGs construits par RPL. Dans notre première contribution, le problème est modélisé comme un problème de couverture minimale des sommets (VCP) sur le DODAG. Nous avons développé un algorithme à temps polynomial qui transforme le DODAG en une décomposition arborescente (Nice-Tree Decomposition) avec une largeur arborescente (treewidth) d’unité. Cette stratégie profite de la spécificité des DODAG et a abouti à une réduction significative de la complexité de la résolution du VCP sur les DODAG. Elle peut être résolue en temps polynomial.La deuxième proposition est un modèle approché pour l’optimisation de l’ordonnancement du rôle de monitorage des nœuds dans les réseaux IdO, afin de maximiser la durée de vie des dispositifs embarqués à ressources limitées, tout en minimisant le coût global du monitorage de réseau. Le monitorage de réseau est très coûteux, en particulier pour les réseaux à ressources limitées tels que l’IdO. Par conséquent, le monitorage doit être économe en énergie et avec des frais généraux minimaux sur la performance normale du réseau. Notre travail correspondant contient une proposition d’un modèle mathématique en trois phases pour assurer l’exigence d’une couverture des moniteurs tout en minimisant la consommation d’énergie de monitorage et les frais de communication.Notre modèle proposé décompose le problème abordé en trois problèmes d’optimisation bien connus, il s’agit du problème de couverture de sommets, problème d’affectation généralisé multi-objectives et problème de voyageur de commerce.Dans cette troisième partie, une approche exacte est proposée pour résoudre le problème décrit dans (Contribution 2). Comme nous avons vu, la décomposition en trois phases ne donne pas la solution exacte. Nous avons donc proposé une formulation exacte du problème qui consiste en un problème de l'affectation minimum des tâches de surveillance avec un fonctionnement de surveillance cyclique. Pour cela, nous avons formulé un programme en nombres entiers binaires. L'ordonnancement optimal garantit la couverture du graphe pour la surveillance avec une consommation d'énergie minimale.

By connecting billions of things to the Internet, IoT created a plethora of applications that touch every aspect of human life. Time-sensitive, mission-critical services, require robust connectivity and strict reliability constraints. On the other hand, the IoT relies mainly on Low-power Lossy Networks, which are unreliable by nature due to their limited resources, hard duty cycles, dynamic topologies, and uncertain radio connectivity. Faults in LLNs are common rather than rare events, therefore, maintaining continuous availability of devices and reliability of communication, are critical factors to guarantee a constant, reliable flow of application data.After a comprehensive literature review, and up to our knowledge, it is clear that there is a call for a new approach to monitoring the unreliable nodes and links in an optimized, energy-efficient, proactive manner, and complete interoperability with IoT protocols. To target this research gap, our contributions address the correct assignment (placement) of the monitoring nodes. This problem is known as the minimum assignment problem, which is NP-hard. We target scalable monitoring by mapping the assignment problem into the well-studied MVC problem, also NP-hard. We proposed an algorithm to convert the DODAG into a nice-tree decomposition with its parameter (treewidth) restricted to the value one. As a result of these propositions, the monitor placement becomes only Fixed-Parameter Tractable, and can also be polynomial-time solvable.To prolong network longevity, the monitoring role should be distributed and balanced between the entire set of nodes. To that end, assuming periodical functioning, we propose in a second contribution to schedule between several subsets of nodes; each is covering the entire network. A three-phase centralized computation of the scheduling was proposed. The proposition decomposes the monitoring problem and maps it into three well-known sub-problems, for which approximation algorithms already exist in the literature. Thus, the computational complexity can be reduced.However, the one major limitation of the proposed three-phase decomposition is that it is not an exact solution. We provide the exact solution to the minimum monitor assignment problem with a duty-cycled monitoring approach, by formulating a Binary Integer Program (BIP). Experimentation is designed using network instances of different topologies and sizes. Results demonstrate the effectiveness of the proposed model in realizing full monitoring coverage with minimum energy consumption and communication overhead while balancing the monitoring role between nodes.The final contribution targeted the dynamic distributed monitoring placement and scheduling. The dynamic feature of the model ensures real-time adaptation of the monitoring schedule to the frequent instabilities of networks, and the distributed feature aims at reducing the communication overhead.; Les réseaux « Internet des Objets » se composent de plusieurs millions d’objets qui possèdent une adresse IP et qui peuvent connecter sur Internet. En général, ces objets sont supposé d’être autonomes et peuvent résoudre des tâches; mesurer, traiter et fournir des informations pour les systèmes connectés et pour les utilisateurs. Aussi, ces réseaux sont vulnérables (c.-à-d. : les éléments peuvent être mobiles et la topologie du réseau peut changer dynamiquement), les changements peuvent influencer le (bon) fonctionnement du réseau. De plus, ils peuvent être alimentés par des batteries de durée de vie limitée, ce que nécessite la réduction de leur consommation.Ce travail de thèse aborde un sujet important dans le domaine de l’Internet des Objets, qui consiste à savoir comment assurer la robustesse et le fonctionnement tolérant aux pannes du réseau pour répondre aux exigences des missions critiques. Avec le large déploiement des services IdO, ce problème est deventé ou de détection de pannes et de sécurité industriel où l’état des objets communicants doit être constamment vérifié pour le rétablissement rapide en cas de problème particulièrement crucial pour les applications telles que le monitorage intelligent de sames de communication inattendus. On cherche alors de minimiser le coût du monitorage et l’utilisation de l’énergie, et aussi les charges additionnelles sur les réseaux.Nous avons proposé un algorithme qui vise à réaliser un placement distribué des moniteurs avec une complexité minimale pour le calcul. L’algorithme proposé fonctionne avec RPL. L’objectif principal est d’augmenter la robustesse dans les réseaux IdO ciblant les applications critiques en temps réel via le monitorage des liaisons dans les DODAGs construits par RPL. Dans notre première contribution, le problème est modélisé comme un problème de couverture minimale des sommets (VCP) sur le DODAG. Nous avons développé un algorithme à temps polynomial qui transforme le DODAG en une décomposition arborescente (Nice-Tree Decomposition) avec une largeur arborescente (treewidth) d’unité. Cette stratégie profite de la spécificité des DODAG et a abouti à une réduction significative de la complexité de la résolution du VCP sur les DODAG. Elle peut être résolue en temps polynomial.La deuxième proposition est un modèle approché pour l’optimisation de l’ordonnancement du rôle de monitorage des nœuds dans les réseaux IdO, afin de maximiser la durée de vie des dispositifs embarqués à ressources limitées, tout en minimisant le coût global du monitorage de réseau. Le monitorage de réseau est très coûteux, en particulier pour les réseaux à ressources limitées tels que l’IdO. Par conséquent, le monitorage doit être économe en énergie et avec des frais généraux minimaux sur la performance normale du réseau. Notre travail correspondant contient une proposition d’un modèle mathématique en trois phases pour assurer l’exigence d’une couverture des moniteurs tout en minimisant la consommation d’énergie de monitorage et les frais de communication.Notre modèle proposé décompose le problème abordé en trois problèmes d’optimisation bien connus, il s’agit du problème de couverture de sommets, problème d’affectation généralisé multi-objectives et problème de voyageur de commerce.Dans cette troisième partie, une approche exacte est proposée pour résoudre le problème décrit dans (Contribution 2). Comme nous avons vu, la décomposition en trois phases ne donne pas la solution exacte. Nous avons donc proposé une formulation exacte du problème qui consiste en un problème de l'affectation minimum des tâches de surveillance avec un fonctionnement de surveillance cyclique. Pour cela, nous avons formulé un programme en nombres entiers binaires. L'ordonnancement optimal garantit la couverture du graphe pour la surveillance avec une consommation d'énergie minimale.

The modern mathematical study of epidemics has adopted the concept of contact networks to model a disease spreading among nodes who may interact with each other along edges. While much progress has been made in designing effective countermeasures against epidemics by acting upon the disease, fewer studies have explored the use of modifying the contact network itself.This thesis explores the possibility of finding an optimal modification of a network to stop an epidemic spreading over it. Because this optimization problem is computationally hard to solve, we design a randomized approximation algorithm by combining semidefinite programming together with matrix concentration inequalities which is guaranteed to return a network modification that stops the epidemic in a short amount of time. Furthermore, we give evidence that the analysis of this algorithm is tight in a large regime.To understand the practical applicability of this algorithm, we analyze current practices in the experimental evaluation of algorithms and propose a new methodology to assess algorithms that may fail, may return approximate solutions, and may change behavior based on hyperparameters.; Les théories mathématiques en épidémiologie ont adopté l'usage de réseaux d'intéractions pour modéliser la propagation d'une épidémie au sein d'une population de nœuds qui sont en contact s'ils sont reliés par une arête. Bien que des avancées majeures aient été réalisées pour concevoir des contre-mesures efficaces qui agissent directement sur les maladies, peu d'études en comparaison ont été effectuées pour tenter de modifier le réseau d'interaction lui-même.Cette thèse étudie la possibilité de trouver une modification optimale d'un réseau de manière à stopper une épidémie qui s'y propagerait. Ce problème d'optimisation étant difficile du point de vue la théorie de la complexité, nous proposons un algorithme probabiliste d'approximation qui est guaranti de produire une modification stoppant l'épidémie en un temps limité. De plus, nous montrons que l'analyse du ratio d'approximation de cet algorithme est la meilleure possible pour un large ensemble d'instances.Pour mesurer l'utilité pratique d'un tel algorithme, nous procédons à une analyse critique des méthodologies actuelles en évaluation expérimentale des algorithmes. En réponse, nous proposons une nouvelle méthodologie pour étudier des implantations d'algorithmes produisant des solutions potentiellement inexactes, sous-optimales et dont le comportement dépend de paramètres.