Dans le cadre du projet européen SESAR, la nécessité d'accroître la capacité du trafic aérien a motivé la planification de trajectoires avions 4D (espace + temps). Afin de mettre en place une planification pré-tactique (évitement de zones avec une mauvaise météo ou congestionnées pour un avion) et de mettre en place une planification tactique (générer des ensembles de trajectoires 4D sans conflit), nous introduisons un nouvel algorithme : l'algorithme de propagation de la lumière (APL). Cet algorithme est basé sur une méthode de propagation de front d'onde qui s'inspire de l'analogie avec la propagation de la lumière et qui est adapté au problème de planification de trajectoires. L'APL donne des résultats satisfaisant pour une journée de trafic réel sur la France tout en satisfaisant les contraintes spécifiques à la gestion du trafic aérien. L'APL a ensuite été adapté pour prendre en compte les incertitudes qui concernent la vitesse réelle des avions. Ainsi adapté aux incertitude, l'APL a été testé sur la même journée de trafic avec mise en place de points RTA (Real Time Arrival). Les points RTA permettent de réduire l'incertitude dans le cas où l'APL n'arrive pas à résoudre les conflits. Les résultats obtenus sont très encourageants.

Le problème de gestion de projet à contraintes de ressources est un des problèmesles plus étudiés dans la littérature. Il consiste à planifier des activités soumises à desrelations de précédence, et nécessitant des ressources renouvelables. L’objectif est deminimiser la durée du projet, soit le makespan. Nous étudions le problème de gestion deprojet à contraintes de ressources. Nous nous sommes intéressées à la résolution exactedu problème. Dans la première partie de la thèse, nous élaborons une série de bornesinférieures basées sur le raisonnement énergétique et des formulations mathématiques.Les résultats montrent que les bornes proposées surpassent ceux de la littérature. Dansla deuxième partie, nous proposons des procédures par séparation et évaluation utilisantles bornes inférieures dévelopées dans la première partie. / Resource Constrained Project Scheduling Problem is one of the most studied schedulingproblems in the literature. It consists in scheduling activities, submitted to precedencerelationship, and requiring renewable resources to be processed. The objective isto minimize the project duration, i.e., the makespan. We study the Resource ConstrainedProject Scheduling Problem. We are interested on the exact resolution of the problem.In the first part of the thesis, we develop a series of lower bounds based on energeticreasoning and mathematical formulations. The computational results show that theproposed lower bounds outperform the ones of the literature. In the second part, wepropose Branch-and-Bound procedures using the lower bounds developed on the firstpart.

En raison de la capacité et de l'amélioration des performances informatiques, les représentations structurelles sont devenues de plus en plus populaires dans le domaine de la reconnaissance de formes (RF). Quand les objets sont structurés à base de graphes, le problme de la comparaison d'objets revient à un problme d'appariement de graphes (Graph Matching). Au cours de la dernière décennie, les chercheurs travaillant dans le domaine de l'appariement de graphes ont porté une attention particulière à la distance d'édition entre graphes (GED), notamment pour sa capacité à traiter différent types de graphes. GED a été ainsi appliquée sur des problématiques spécifiques qui varient de la reconnaissance de molécules à la classi fication d'images. / Due to the inherent genericity of graph-based representations, and thanks to the improvement of computer capacities, structural representations have become more and more popular in the field of Pattern Recognition (PR). In a graph-based representation, vertices and their attributes describe objects (or part of them) while edges represent interrelationships between the objects. Representing objects by graphs turns the problem of object comparison into graph matching (GM) where correspondences between vertices and edges of two graphs have to be found.

Orientador: Ariovaldo Verandio Garcia, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T06:56:43Z (GMT). No. of bitstreams: 1 RiderFlores_MarcosJulio_D.pdf: 1021887 bytes, checksum: 6000961c2f5457b410ac691912476270 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho são propostos modelos matemáticos e técnicas de solução para resolver o problema de planejamento da expansão de sistemas de transmissão através de três enfoques. a) Usando o modelo de corrente alternada do sistema de transmissão e um algoritmo heurístico construtivo especializado para resolver o problema de planejamento, e, ainda, realiza-se uma primeira tentativa de alocação de fontes de potência reativas; b) Usando o modelo de corrente contínua e técnicas de programação não-linear especializadas. Nesse caso emprega-se uma versão relaxada do problema de planejamento da expansão de sistemas de transmissão usando o modelo de corrente contínua, onde a integralidade das variáveis de investimento é desprezada. Resolve-se o problema de programação não-linear, modelado de forma matricial com um algoritmo de otimização especializado e, além disso, um algoritmo heurístico construtivo especializado é utilizado para resolver o problema de planejamento. c) Usando o modelo de corrente contínua e um algoritmo Branch and Bound (B&B) sem empregar técnicas de decomposição. Para isso foram redefinidos os chamados testes de sondagem no algoritmo B&B e em cada nó da árvore de B&B tem-se um problema de programação não-linear que são resolvidos usando a metodologia desenvolvida no item (b). Os ítens (a), (b) e (c) requerem a solução de problemas de programação não-linear diferenciados. Uma revisão das características principais da resolução iterativa dos métodos de pontos interiores é apresentada. Foi desenvolvida uma técnica baseada em uma combinação de métodos de pontos interiores de alta ordem (MPI-AO) para resolver os problemas de programação não-linear de forma rápida, eficiente e robusta. Essa combinação dos MPI-AO tem como objetivo colocar num único método as características particulares de cada um dos MPI-AO e melhorar o desempenho computacional comparado com os MPI-AO de forma individual / Abstract: In this work mathematical models and solution techniques are proposed to solve the power system transmission expansion planning problem through three approaches: a) Using the nonlinear model ofthe transmission system (AC model) and a specialized constructive heuristic algorithm to solve the problem and, yet, a first attempt to allocate reactive power sources is also considered; b) Using the direct-current (DC) model and specialized techniques of nonlinear programming. In this case a version of the power system transmission expansion planning problem using the DC model where the integrality of the investment variables is relaxed is used. The nonlinear programming problem is solved with a specialized optimization algorithm and, moreover, a constructive heuristic algorithm is employed to solve the planning problem. c) Using the DC model and Branch and Bound (B&B) algorithm without the use of decomposition techniques. The so called fathoming tests of the B&B were redefined and at each node of the tree a nonlinear programming problem is solved using the method developed in b). Items a), b) and c) require the solution of distinct problems of nonlinear programming. A revision of the main characteristics of the iterative solution of the interior points methods is presented. An optimization technique based on a combination of the higher order interior point methods (HO-IPM) had been developed to solve the nonlinear programming problems in a fast, efficient and robust way. This combination of the HO-IPM has as objective to explore the particular characteristics of each method in a single one and to improve the comparative computational performance with the HO-IPM of individual form / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

La plupart des travaux de recherches sur les problèmes d'ordonnancement traitent le cas des ressources renouvelables, c'est-à-dire des ressources qui sont exigées en début d'exécution de chaque tâche et sont restituées en fin d'exécution. Peu d'entre eux abordent les problèmes à ressources consommables, c'est-à-dire des ressources non restituées en fin d'exécution. Le problème de gestion de projet à contraintes de ressources (RCPSP) est le problème à ressources renouvelables le plus traité dans la littérature. Dans le cadre de cette thèse, nous nous sommes intéressés à une généralisation du problème RCPSP qui correspond au cas où les tâches sont remplacées par des événements liés par des relations de précédence étendues. Chaque événement peut produire ou consommer une quantité de ressources à sa date d'occurrence et la fonction économique reste la durée totale à minimiser. Nous avons nommé cette généralisation ERCPSP (Extended RCPSP). Nous avons élaboré des modèles de programmation linéaire pour résoudre ce problème. Nous avons proposé plusieurs bornes inférieures algorithmiques exploitant les travaux de la littérature sur les problèmes cumulatifs. Ensuite, nous avons élargi la portée des méthodes utilisées pour la mise en place de méthodes de séparation et évaluation. Nous avons traité aussi des cas particuliers par des méthodes basées sur la programmation dynamique. / This thesis investigates the Extended Resource Constrained Project Scheduling Problem (ERCPSP). ERCPSP is a general scheduling problem where the availability of a resource is depleted and replenished at the occurrence times of a set of events. It is an extension of the Resource Constrained Project Scheduling Problem (RCPSP) where activities are replaced by events, which have to be scheduled subject to generalized precedence relations. We are interested in this thesis in proposing new methodologies and approaches to solve ERCPSP. First, we study some polynomial cases of this problem and we propose a dynamic programming algorithm to solve the parallel chain case. Then, we propose lower bounds, mixed integer programming models, and a branch-and-bound method to solve ERCPSP. Finally, we develop an instance generator dedicated to this problem.

On s'attache dans cette thèse à plusieurs aspects liés à la résolution de problèmes multi-objectifs, sans se limiter au cas biobjectif. Nous considérons la résolution exacte, dans le sens de la détermination de l'ensemble des points non dominés, ainsi que la résolution approchée dans laquelle on cherche une approximation de cet ensemble dont la qualité est garantie a priori.Nous nous intéressons d'abord au problème de la détermination d'une représentation explicite de la région de recherche. La région de recherche, étant donné un ensemble de points réalisables connus, exclut la partie de l'espace des objectifs que dominent ces points et constitue donc la partie de l'espace des objectifs où les efforts futurs doivent être concentrés dans la perspective de déterminer tous les points non dominés.Puis nous considérons le recours aux algorithmes de séparation et évaluation ainsi qu'aux algorithmes de ranking afin de proposer une nouvelle méthode hybride de détermination de l'ensemble des points non dominés. Nous montrons que celle-ci peut également servir à obtenir une approximation de l'ensemble des points non dominés. Cette méthode est implantée pour le problème de l'arbre couvrant de poids minimal. Les quelques propriétés de ce problème que nous passons en revue nous permettent de spécialiser certaines procédures et d'intégrer des prétraitements spécifiques. L'intérêt de cette approche est alors soutenu à l'aide de résultats expérimentaux. / This thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori guarantee on the quality.We first consider the determination of an explicit representation of the search region. The search region, defined with respect to a set of known feasible points, excludes from the objective space the part which is dominated by these points. Future efforts to find all nondominated points should therefore be concentrated on the search region.Then we review branch and bound and ranking algorithms and we propose a new hybrid approach for the determination of the nondominated set. We show how the proposed method can be adapted to generate an approximation of the nondominated set. This approach is instantiated on the minimum spanning tree problem. We review several properties of this problem which enable us to specialize some procedures of the proposed approach and integrate specific preprocessing rules. This approach is finally supported through experimental results.

This thesis presents a predictive energy management controller for long-haul hybrid trucks. In a receding horizon control framework, the vehicle speed reference, battery energy reference, and engine on/off decision are optimized over a prediction horizon. A mixed-integer quadratic program (MIQP) is formulated by performing modelling approximations and by including the binary engine on/off decision in the optimal control problem. The branch-and-bound algorithm is applied to solve this problem. Simulation results show fuel consumption reductions between 10-15%, depending on driving cycle, compared to a conventional truck. The hybrid truck without the predictive control saves significantly less. Fuel consumption is reduced by 3-8% in this case. A sensitivity analysis studies the effects on branch-and-bound iterations and fuel consumption when varying parameters related to the binary engine on/off decision. In addition, it is shown that the control strategy can maintain a safe time gap to a leading vehicle. Also, the introduction of the battery temperature state makes it possible to approximately model the dynamic battery power limitations over the prediction horizon. The main contributions of the thesis are the MIQP control problem formulation, the strategy to solve this with the branch-and-bound method, and the sensitivity analysis.

L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3. / Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

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.