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.

Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations / In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations

Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces. / In this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature.

Basés sur les outils théoriques et algorithmiques de la programmation DC et DCA, les travaux de recherche dans cette thèse portent sur les approches locales et globales pour l'optimisation non convexe et l'optimisation globale en variables mixtes entières. La thèse comporte 5 chapitres. Le premier chapitre présente les fondements de la programmation DC et DCA, et techniques de Séparation et Evaluation (B&B) (utilisant la technique de relaxation DC pour le calcul des bornes inférieures de la valeur optimale) pour l'optimisation globale. Y figure aussi des résultats concernant la pénalisation exacte pour la programmation en variables mixtes entières. Le deuxième chapitre est consacré au développement d'une méthode DCA pour la résolution d'une classe NP-difficile des programmes non convexes non linéaires en variables mixtes entières. Ces problèmes d'optimisation non convexe sont tout d'abord reformulées comme des programmes DC via les techniques de pénalisation en programmation DC de manière que les programmes DC résultants soient efficacement résolus par DCA et B&B bien adaptés. Comme première application en optimisation financière, nous avons modélisé le problème de gestion de portefeuille sous le coût de transaction concave et appliqué DCA et B&B à sa résolution. Dans le chapitre suivant nous étudions la modélisation du problème de minimisation du coût de transaction non convexe discontinu en gestion de portefeuille sous deux formes : la première est un programme DC obtenu en approximant la fonction objectif du problème original par une fonction DC polyèdrale et la deuxième est un programme DC mixte 0-1 équivalent. Et nous présentons DCA, B&B, et l'algorithme combiné DCA-B&B pour leur résolution. Le chapitre 4 étudie la résolution exacte du problème multi-objectif en variables mixtes binaires et présente deux applications concrètes de la méthode proposée. Nous nous intéressons dans le dernier chapitre à ces deux problématiques challenging : le problème de moindres carrés linéaires en variables entières bornées et celui de factorisation en matrices non négatives (Nonnegative Matrix Factorization (NMF)). La méthode NMF est particulièrement importante de par ses nombreuses et diverses applications tandis que les applications importantes du premier se trouvent en télécommunication. Les simulations numériques montrent la robustesse, rapidité (donc scalabilité), performance et la globalité de DCA par rapport aux méthodes existantes. / Based on theoretical and algorithmic tools of DC programming and DCA, the research in this thesis focus on the local and global approaches for non convex optimization and global mixed integer optimization. The thesis consists of 5 chapters. The first chapter presents fundamentals of DC programming and DCA, and techniques of Branch and Bound method (B&B) for global optimization (using the DC relaxation technique for calculating lower bounds of the optimal value). It shall include results concerning the exact penalty technique in mixed integer programming. The second chapter is devoted of a DCA method for solving a class of NP-hard nonconvex nonlinear mixed integer programs. These nonconvex problems are firstly reformulated as DC programs via penalty techniques in DC programming so that the resulting DC programs are effectively solved by DCA and B&B well adapted. As a first application in financial optimization, we modeled the problem pf portfolio selection under concave transaction costs and applied DCA and B&B to its solutions. In the next chapter we study the modeling of the problem of minimization of nonconvex discontinuous transaction costs in portfolio selection in two forms: the first is a DC program obtained by approximating the objective function of the original problem by a DC polyhedral function and the second is an equivalent mixed 0-1 DC program. And we present DCA, B&B algorithm, and a combined DCA-B&B algorithm for their solutions. Chapter 4 studied the exact solution for the multi-objective mixed zero-one linear programming problem and presents two practical applications of proposed method. We are interested int the last chapter two challenging problems: the linear integer least squares problem and the Nonnegative Mattrix Factorization problem (NMF). The NMF method is particularly important because of its many various applications of the first are in telecommunications. The numerical simulations show the robustness, speed (thus scalability), performance, and the globality of DCA in comparison to existent methods.