著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.

L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentée.

On-orbit servicing (OOS) of space systems provides immense benefits by extending their lifetime, by reducing overall cost of space operations, and by adding flexibility to space missions. Refueling is an important aspect of OOS operations. The problem of determining the optimal strategy of refueling multiple satellites in a constellation, by expending minimum fuel during the orbital transfers, is challenging, and requires the solution of a large-scale optimization problem. The conventional notion about a refueling mission is to have a service vehicle visit all fuel-deficient satellites one by one and deliver fuel to them. A recently emerged concept, known as the peer-to-peer (P2P) strategy, is a distributed method of replenishing satellites with fuel. P2P strategy is an integral part of a mixed refueling strategy, in which a service vehicle delivers fuel to part (perhaps half) of the satellites in the constellation, and these satellites, in turn, engage in P2P maneuvers with the remaining satellites. During a P2P maneuver between a fuel-sufficient and a fuel-deficient satellite, one of them performs an orbital transfer to rendezvous with the other, exchanges fuel, and then returns back to its original orbital position. In terms of fuel expended during the refueling process, the mixed strategy outperforms the single service vehicle strategy, particularly with increasing number of satellites in the constellation. This dissertation looks at the problem of P2P refueling problem and proposes new extensions like the Cooperative P2P and Egalitarian P2P strategies. It presents an overview of the methodologies developed to determine the optimal set of orbital transfers required for cooperative and non-cooperative P2P refueling strategies. Results demonstrate that the proposed strategies help in reducing fuel expenditure during the refueling process.

Les travaux présentes dans cette thèse s'inscrivent dans le cadre des méthodes d'évacuation des populations. Ils visent à étudier les capacités et modéliser le problème d'évacuation (blessés, sinistrés, enfants, personnes agées, etc.) dans une situation de crise (attentats terroristes, catastrophes naturelles, etc.) et développer des méthodes d'aide à la décision tout en proposant une meilleure planification et des plans optimaux d'évacuation des populations de la zone de crise vers les centres hospitaliers.Notre travail consiste à résoudre le problème d'évacuation de blessés dans des zones de crise avec une nouvelle vision qui consiste à optimiser le temps de transport et par conséquent sauver le maximum des personnes touchées par cette crise d'une façon dynamique, efficace et rapide pour minimiser la perte humaine. / The work presented in this thesis is part of human evacuation methods. It aims to study the capacities, model the evacuation problem (wounded, victims, children, elderly, etc.) in a crisis situation (terrorist attacks, natural disasters, etc.) and to develops methods for decision making while proposing better planning and optimal evacuation plans for populations from the crisis zone to hospitals.Our job is to solve the wounded evacuation problem in crisis zone with a new vision that optimizes the transport time and thus saving the maximum of causalities in a dynamic, efficient and fast way in order to minimize human loss.

Made available in DSpace on 2014-12-17T14:52:43Z (GMT). No. of bitstreams: 1 AnaCGS.pdf: 4192359 bytes, checksum: 28eb36354363672f88a28074f9df8b42 (MD5) Previous issue date: 2008-12-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Telecommunications play a key role in contemporary society. However, as new technologies are put into the market, it also grows the demanding for new products and services that depend on the offered infrastructure, making the problems of planning telecommunications networks, despite the advances in technology, increasingly larger and complex. However, many of these problems can be formulated as models of combinatorial optimization, and the use of heuristic algorithms can help solving these issues in the planning phase. In this project it was developed two pure metaheuristic implementations Genetic algorithm (GA) and Memetic Algorithm (MA) plus a third hybrid implementation Memetic Algorithm with Vocabulary Building (MA+VB) for a problem in telecommunications that is known in the literature as Problem SONET Ring Assignment Problem or SRAP. The SRAP arises during the planning stage of the physical network and it consists in the selection of connections between a number of locations (customers) in order to meet a series of restrictions on the lowest possible cost. This problem is NP-hard, so efficient exact algorithms (in polynomial complexity ) are not known and may, indeed, even exist / As telecomunica??es desempenham um papel fundamental na sociedade contempor?nea. Mas ? medida que novas tecnologias s?o introduzidas ao mercado, cresce tamb?m a demanda por novos produtos e servi?os que dependem da infra-estrutura oferecida, tornando os problemas de planejamento de redes de telecomunica??es, apesar da evolu??o tecnol?gica, cada vez maiores e complexos. No entanto, muitos desses problemas podem ser formulados como modelos de otimiza??o combinat?ria, e o uso de algoritmos heur?sticos podem ajudar a solucionar essas quest?es da fase de planejamento. Neste trabalho, foram desenvolvidas duas implementa??es metaheur?sticas puras Algoritmo Gen?tico (AG) e Algoritmo Mem?tico (AM) al?m de uma terceira implementa??o h?brida Algoritmo Mem?tico com Vocabulary Building (AM+VB) para um problema de telecomunica??es que ? conhecido na literatura por Problema de Atribui??o de Localidades a An?is SONET ou SRAP (do ingl?s, SONET Ring Assignment Problem). O SRAP surge durante a etapa do planejamento f?sico da rede e consiste na determina??o das conex?es entre um conjunto de localidades (clientes), de modo a satisfazer uma s?rie de restri??es ao menor custo poss?vel. Esse problema ? NP-dif?cil e portanto algoritmos exatos eficientes (de complexidade polinomial) n?o s?o conhecidos, podendo, inclusive, nem existir

Made available in DSpace on 2014-12-17T14:52:44Z (GMT). No. of bitstreams: 1 WernerKSS.pdf: 2229557 bytes, checksum: 7a64dc1b94612cd78d88c6eb822d29e6 (MD5) Previous issue date: 2009-10-31 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The SONET/SDH Ring Assignment Problem (PALAS) treats to group localities in form of some rings, being respected the traffic's limitations of the equipment. Each ring uses a DXC (Digital Cross Connect) to make the communication with the others, being the DXC the equipment most expensive of the net, minimizing the number total of rings, will minimize the total net cost, problem's objective . This topology in rings provides a bigger capacity of regeneration. The PALAS is a problem in Combinatorial Optimization of NP-hard Class. It can be solved through Heuristics and Metaheuristics. In this text, we use Taboo Search while we keep a set of elite solutions to be used in the formation of a part of the collection of vocabulary's parts that in turn will be used in the Vocabulary Building. The Vocabulary Building will be started case Taboo Search does not reach the best solution for the instance. Three approaches had been implemented: one that only uses vocabulary's parts deriving of Taboo Search, one that it only uses vocabulary's parts randomly generated and a last one that it uses half come of the elite and half randomly generated / O Problema da Atribui??o de Localidades a An?is em Redes SONET/SDH (PALAS) trata de agrupar localidades em forma de v?rios an?is, respeitando as limita??es de tr?fego dos equipamentos. Cada anel utiliza um DXC (Digital Cross Connect) para fazer a comunica??o com os outros, sendo o DXC o equipamento mais caro da rede, minimizando o total de an?is, minimizaremos o custo total, objetivo do problema. Essa topologia em an?is proporciona uma maior capacidade de regenera??o. O PALAS ? um problema de Otimiza??o Combinat?ria da Classe NP-dif?cil. Pode ser resolvido atrav?s de Heur?sticas e Metaheur?sticas. Neste trabalho, utilizamos a Busca Tabu enquanto guardamos um conjunto de solu??es elite para serem utilizadas na forma??o de uma parte da cole??o de voc?bulos que por sua vez ser?o usados na Constru??o de Vocabul?rio para a solu??o desse problema. A Constru??o de Vocabul?rio ser? acionada caso a Busca Tabu n?o atinja o ?timo para a inst?ncia. Foram implementadas tr?s abordagens: uma que utiliza somente voc?bulos oriundos da Busca Tabu, uma que utiliza somente voc?bulos gerados aleatoriamente e uma ?ltima que utiliza metade vinda da elite e metade aleat?ria

Made available in DSpace on 2014-12-17T14:52:49Z (GMT). No. of bitstreams: 1 WagnerO_DISSERT.pdf: 4964124 bytes, checksum: 34ed6ffd6dcd720ddf12631ffd06a3d6 (MD5) Previous issue date: 2010-03-17 / The telecommunications play a fundamental role in the contemporary society, having as one of its main roles to give people the possibility to connect them and integrate them into society in which they operate and, therewith, accelerate development through knowledge. But as new technologies are introduced on the market, increases the demand for new products and services that depend on the infrastructure offered, making the problems of planning of telecommunication networks become increasingly large and complex. Many of these problems, however, can be formulated as combinatorial optimization models, and the use of heuristic algorithms can help solve these issues in the planning phase. This paper proposes the development of a Parallel Evolutionary Algorithm to be applied to telecommunications problem known in the literature as SONET Ring Assignment Problem SRAP. This problem is the class NP-hard and arises during the physical planning of a telecommunication network and consists of determining the connections between locations (customers), satisfying a series of constrains of the lowest possible cost. Experimental results illustrate the effectiveness of the Evolutionary Algorithm parallel, over other methods, to obtain solutions that are either optimal or very close to it / As telecomunica??es desempenham um papel fundamental na sociedade contempor?nea, tendo como um de seus principais pap?is o de conceder ?s pessoas a possibilidade de conect?-las e integr?-las ? sociedade em que vivem e com isso acelerar o desenvolvimento por meio do conhecimento. Mas, ? medida que novas tecnologias s?o introduzidas no mercado, cresce tamb?m a demanda por novos produtos e servi?os que dependem da infraestrutura oferecida, tornando os problemas de planejamento de redes de telecomunica??es cada vez maiores e mais complexos. Muitos desses problemas, no entanto, podem ser formulados como modelos de Otimiza??o Combinat?ria, e o uso de algoritmos heur?sticos podem ajudar a solucionar essas quest?es da fase de planejamento. Este trabalho prop?e o desenvolvimento de um Algoritmo Evolutivo paralelo a ser aplicado ao problema de telecomunica??es conhecido na literatura por Problema de Atribui??o de Localidades a An?is em Redes SONET/SDH ou PALAS. Esse problema ? da classe NP-dif?cil e surge durante a etapa do planejamento f?sico da rede e consiste na determina??o das conex?es entre localidades (clientes), de modo a satisfazer uma s?rie de restri??es ao menor custo poss?vel. Os resultados dos experimentos ilustram a efici?ncia do Algoritmo Evolutivo paralelo, sobre outros m?todos, em obter solu??es ?timas ou muito pr?ximas do valor ?timo

Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation. / Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.

La présente thèse a pour objectif principal de développer des approches déterministes et heuristiques pour résoudre certaines classes de problèmes d'optimisation en Finance, Affectation et Recherche d’Informations. Il s’agit des problèmes d’optimisation non convexe de grande dimension. Nos approches sont basées sur la programmation DC&DCA et la méthode Cross-Entropy (CE). Grâce aux techniques de formulation/reformulation, nous avons donné la formulation DC des problèmes considérés afin d’obtenir leurs solutions en utilisant DCA. En outre, selon la structure des ensembles réalisables de problèmes considérés, nous avons conçu des familles appropriées de distributions pour que la méthode Cross-Entropy puisse être appliquée efficacement. Toutes ces méthodes proposées ont été mises en œuvre avec MATLAB, C/C++ pour confirmer les aspects pratiques et enrichir notre activité de recherche. / In this thesis we focus on developing deterministic and heuristic approaches for solving some classes of optimization problems in Finance, Assignment and Search Information. They are large-scale nonconvex optimization problems. Our approaches are based on DC programming & DCA and the Cross-Entropy method. Due to the techniques of formulation/reformulation, we have given the DC formulation of considered problems such that we can use DCA to obtain their solutions. Also, depending on the structure of feasible sets of considered problems, we have designed appropriate families of distributions such that the Cross-Entropy method could be applied efficiently. All these proposed methods have been implemented with MATLAB, C/C++ to confirm the practical aspects and enrich our research works.

This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.