Several techniques were studied to select and prioritize technologies for a complex system. Based on the findings, a method called Pareto Optimization and Selection of Technologies (POST) was formulated to efficiently explore the combinatorial technology space. A knapsack problem was selected as a benchmark problem to test-run various algorithms and techniques of POST. A Monte Carlo simulation using the surrogate models was used for uncertainty quantification. The concepts of graph theory were used to model and analyze compatibility constraints among technologies. A probabilistic Pareto optimization, based on the concepts of Strength Pareto Evolutionary Algorithm II (SPEA2), was formulated for Pareto optimization in an uncertain objective space. As a result, multiple Pareto hyper-surfaces were obtained in a multi-dimensional objective space; each hyper-surface representing a specific probability level. These Pareto layers enabled the probabilistic comparison of various non-dominated technology combinations. POST was implemented on a technology exploration problem for a 300 passenger commercial aircraft. The problem had 29 identified technologies with uncertainties in their impacts on the system. The distributions for these uncertainties were defined using beta distributions. Surrogate system models in the form of Response Surface Equations (RSE) were used to map the technology impacts on the system responses. Computational complexity of technology graph was evaluated and it was decided to use evolutionary algorithm for probabilistic Pareto optimization. The dimensionality of the objective space was reduced using a dominance structure preserving approach. Probabilistic Pareto optimization was implemented with reduced number of objectives. Most of the technologies were found to be active on the Pareto layers. These layers were exported to a dynamic visualization environment enabled by a statistical analysis and visualization software called JMP. The technology combinations on these Pareto layers are explored using various visualization tools and one combination is selected. The main outcome of this research is a method based on consistent analytical foundation to create a dynamic tradeoff environment in which decision makers can interactively explore and select technology combinations.

Made available in DSpace on 2016-12-12T20:22:53Z (GMT). No. of bitstreams: 1 LEANDERSON ANDRE.pdf: 2236080 bytes, checksum: a52e91a8b1a8e6a12497786254e94344 (MD5) Previous issue date: 2015-08-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nature offers a wide range of phenomena that inspire the development of new technologies. The researchers from the area of Natural Computing abstracts the concept of optimization from various biological processes such as the evolution of species, the behavior of social groups, the search for food, among others. Such computer systems that have a similarity to natural biological systems are called biologically plausible. The development of biologically plausible algorithms gets interesting by the fact that biological systems are able to handle extremely complex problems. In this way, symbiotic relationships are one of several phenomena that can be observed in nature. These relationships consist of interactions that organisms carry out with each other resulting in benefit or disadvantage to those involved. In an optimization context, symbiotic relationships can be used to perform exchange of information between populations of candidate solutions to a given problem. Thus, this work highlights the concepts involving symbiotic relationships that may be important for the development of computer systems to solve complex problems. The main discussion presented in this study refers to the use of symbiotic relationships between populations of candidate solutions co-evolving in an ecological context. According to the analogy, populations interact with each other according to a specific symbiotic relationship in order to evolve their solutions. The proposed model is applied to several continuous benchmark functions with a high number of dimensions (D = 200) and in several benchmark instances of the multiple knapsack problem. The results obtained so far were promising concerning the application of symbiotic relationships. Finally, the conclusions are presented and some future directions for research are suggested. / A Natureza apresenta uma grande variedade de fenômenos que inspiram o desenvolvimento de novas tecnologias. Os pesquisadores da área de Computação Natural abstraem o conceito de otimização de vários processos biológicos, tais como a evolução das espécies, comportamento de grupos sociais, busca por comida, dentre outros. Tais sistemas computacionais que apresentam uma semelhança com os sistemas biológicos naturais são chamados de biologicamente plausíveis. O desenvolvimento de algoritmos biologicamente plausíveis se torna interessante pelo fato de que os sistemas biológicos são capazes de lidar com problemas extremamente complexos. As relações simbióticas são um dos vários fenômenos que podem ser observados na natureza. Essas relações consistem de interações que organismos realizam entre si resultando em benefícios ou prejuízos para os envolvidos. Em um contexto de otimização, as relações simbióticas podem ser utilizadas para realizar a troca de informação entre populações de soluções candidatas para um dado problema. Desta forma, este trabalho destaca os conceitos que envolvem as relações simbióticas que podem ser importantes para o desenvolvimento de sistemas computacionais para a resolução de problemas complexos. A principal discussão apresentada nesse trabalho refere-se a utilização de relações simbióticas entre populações de soluções candidatas, coevoluindo em um contexto ecológico. Com essa analogia, cada população interage com uma outra de acordo com uma relação simbiótica específica, com o objetivo de evoluir suas soluções. O modelo apresentado é aplicado a várias funções benchmark contínuas com um número alto de dimensões (D = 200) e várias instâncias benchmark do problema da mochila múltipla. Os resultados obtidos se mostraram promissores considerando a aplicação das relações simbióticas. Por fim, as conclusões são apresentadas e algumas direções para pesquisas futuras são sugeridas.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

[pt] Um importante ramo do estudo de logística é aquele que se preocupa com a otimização da eficiência do uso de recursos de transporte. No segmento de aviação da Petrobras, que transporta cerca de 20 por cento de todos os passageiros offshore do planeta, otimizações são bastante significativas e podem gerar importantes benefícios econômicos (menor custo total), logísticos (maior disponibilidade de recursos), ambientais (menores emissões de gases poluentes) e de segurança (menor exposição aos riscos da atividade). Por estes motivos, é imperativo que se busque formas de aumentar a eficiência do uso das aeronaves contratadas, maximizando sua utilização dentro de limites permitidos por normas de voo offshore, limites de fadiga de tripulantes, limites operacionais dos aeroportos de origem e destino, além de limites de capacidades de cada aeronave. Neste sentido, o objetivo deste estudo é apresentar o desenvolvimento de soluções para redução dos custos da operação aérea, buscando o máximo aproveitamento das aeronaves contratadas, a partir de uma proposta de otimização da programação de voos através da resolução de um resolução de uma formulação de Programação Linear Inteira, que estende um Problema de Múltiplas Mochilas, respeitando as limitações impostas por regulamentação e necessidades operacionais. Foi desenvolvida uma ferramenta computacional e os resultados obtidos a partir deste trabalho foram implementados nas operações da Petrobras e fazem parte do Plano de Resiliência desta empresa. Os ganhos econômicos obtidos representam uma redução de 100 milhões de reais no quinquênio do Plano de Negócios e Gestão 2020-2024, o que comprova o benefício das soluções implementadas. / [en] An important field of the logistics study is one that is concerned with optimizing the efficiency of the use of transport resources. In Petrobras aviation segment, which transports about 20 percent of all offshore passengers worldwide, optimizations are quite significant and can generate important economic (lower total cost), logistical (increased availability of resources), environmental (lower emissions of polluting gases) and safety (reduced exposure to the risks of the activity) benefits. For these reasons, it is imperative to seek ways to increase efficiency in the use of contracted aircrafts, maximizing their use within the boundaries imposed by offshore flight rules, crew fatigue restrictions, operational restrictions of the origin and destination airports, in addition to capacity limits for each aircraft. Hereupon, the objective of this study is to present the development of solutions to reduce the costs of aerial operation, seeking the maximum use of contracted aircrafts, based on a proposal to optimize the flight schedule through the resolution of an Integer Linear Programming formulation that extends a Multiple Knapsack Problem, but within the boundaries imposed by regulations and operational needs. A computational tool was developed and results obtained from this work were implemented in Petrobras operations, and are part of this company s Resilience Plan. The economic gains obtained represent a reduction of USD 27 million in the five-year period of the 2020-2024 Business Plan, which proves the benefit of the implemented solutions.

No / A membrane-inspired evolutionary algorithm (MIEA) is a successful instance of a model linking membrane computing and evolutionary algorithms. This paper proposes the analysis of dynamic behaviors of MIEAs by introducing a set of population diversity and convergence measures. This is the first attempt to obtain additional insights into the search capabilities of MIEAs. The analysis is performed on the MIEA, QEPS (a quantum-inspired evolutionary algorithm based on membrane computing), and its counterpart algorithm, QIEA (a quantum-inspired evolutionary algorithm), using a comparative approach in an experimental context to better understand their characteristics and performances. Also the relationship between these measures and fitness is analyzed by presenting a tendency correlation coefficient to evaluate the importance of various population and convergence measures, which is beneficial to further improvements of MIEAs. Results show that QEPS can achieve better balance between convergence and diversity than QIEA, which indicates QEPS has a stronger capacity of balancing exploration and exploitation than QIEA in order to prevent premature convergence that might occur. Experiments utilizing knapsack problems support the above made statement.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future. For this problem we analyze the existing mathematical models, propose new models, design a heuristic and two metaheuristic approaches, being their performances improved by using parallel programming, and solve instances, practical and randomly generated, from the literature. The computational experiments were quite good for all tested instances. The second problem we consider is the stable roommates problem (a variant of the stable matching problem). For this we give two mathematical programming models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The last problem we consider is the compartmentalized knapsack problem (a generalization of the knapsack problem) for which we analyze a quadratic integer model and give a linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses path-relinking, and solve randomly generated instances. All parallel implementations use Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos, onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este problema analisamos os modelos matemáticos existentes, propomos novos modelos, projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias, encontradas na literatura; sendo os experimentos computacionais muito bons para todas as intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros estáveis (stable roommates problem), uma variante do problema de emparelhamento estável (stable matching problem). Para este propomos dois modelos matemáticos, uma implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema. O último problema considerado é o da mochila compartimentada (uma generalização do problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente. Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics Processing Units, GPUs).

Le conflit entre la demande de services multimédia en multidiffusion à haut débit (MBMS) et les limites en ressources radio demandent une gestion efficace de l'allocation des ressources radio (RRM) dans les réseaux 3G UMTS. À l'opposé des travaux existant dans ce domaine, cette thèse se propose de résoudre le problème de RRM dans les MBMS par une approche d’optimisation combinatoire. Le travail commence par une modélisation formelle du problème cible, désigné comme Flexible Radio Resource Management Model (F2R2M). Une analyse de la complexité et du paysage de recherche est effectuée à partir de ce modèle. Tout d’abord on montre qu'en assouplissant les contraintes de code OVSF, le problème de RRM pour les MBMS peut s'apparenter à un problème de sac à dos à choix multiples (MCKP). Une telle constatation permet de calculer les limites théoriques de la solution en résolvant le MCKP similaire. En outre, l'analyse du paysage montre que les espaces de recherche sont accidentés et constellés d'optima locaux. Sur la base de cette analyse, des algorithmes métaheuristiques sont étudiés pour résoudre le problème. Nous montrons tout d'abord que un Greedy Local Search (GLS) et un recuit simulé (SA) peuvent trouver de meilleures solutions que les approches existantes implémentées dans le système UMTS, mais la multiplicité des optima locaux rend les algorithmes très instables. Un algorithme de recherche tabou (TS) incluant une recherche à voisinage variable (VNS) est aussi développé et comparé aux autres algorithmes (GLS et SA) et aux approches actuelles du système UMTS ; les résultats de la recherche tabou dépassent toutes les autres approches. Enfin les meilleures solutions trouvées par TS sont également comparées avec les solutions théoriques générées par le solveur MCKP. On constate que les meilleures solutions trouvées par TS sont égales ou très proches des solutions optimales théoriques. / The high throughputs supported by the multimedia multicast services (MBMS) and the limited radio resources result in strong requirement for efficient radio resource management (RRM) in UMTS 3G networks. This PhD thesis proposes to solve the MBMS RRM problem as a combinatorial optimization problem. The work starts with a formal modeling of the problem, named as the Flexible Radio Resource Management Model (F2R2M). An in-depth analysis of the problem complexity and the search landscape is done from the model. It is showed that, by relaxing the OVSF code constraints, the MBMS RRM problem can be approximated as a Multiple-Choice Knapsack Problem (MCKP). Such work allows us to compute the theoretical solution bounds by solving the approximated MCKP. Then the fitness landscape analysis shows that the search spaces are rough and reveal several local optimums. Based on the analysis, some metaheuristic algorithms are studied to solve the MBMS RRM problem. We first show that a Greedy Local Search (GLS) and a Simulated Annealing (SA) allow us to find better solutions than the existing approaches implemented in the UMTS system, however the results are instable due to the landscape roughness. Finally we have developed a Tabu Search (TS) mixed with a Variable Neighborhood Search (VNS) algorithm and we have compared it with GLS, SA and UMTS embedded algorithms. Not only the TS outperforms all the other approaches on several scenarios but also, by comparing it with the theoretical solution bounds generated by the MCKP solver, we observe that TS is equal or close to the theoretical optimal solutions.

This thesis presents description of Genetic algorithm. The description begins with theory of complexity and following basic theory of genetic algorithm. Next part explains the principle of all three tasks – travelling salesman problem, knapsack problem and evolution of algorithm for five-in-a-row. The main focus was on developing the algorithm for five-in-a-row. The results were tested with other similar algorithms from internet. In case of travelling salesman problem and knapsack problem, the results were compared with gradient optimization methods.

L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

Asset management within the nuclear industry has become an increasingly relevant topic as safety requirements have tightened and energy security has become more important. Asset management ensures performance and reliability in a nuclear facility by balancing costs, opportunities, and risks to get the most out of assets. Asset management processes can often be modeled as capital budgeting problems, where investments are evaluated based on costs and benefits, which establishes a link to mathematical optimization. This study addresses asset management at the Swedish nuclear power plant, Forsmark, and aims to implement an optimization model to improve the project selection related to maintenance and replacement of assets at the plant. First, the most relevant areas of nuclear asset management are identified through a comprehensive literature review. The most relevant method, identified as a mix between risk-informed asset management and capital budgeting, is then implemented to fit the prerequisites at Forsmark. Several models of different complexity are developed and the resulting stochastic model incorporates uncertainty of input variables by assuming underlying distributions. Finally, a methodology to incorporate a quantitative risk measure in the optimization is suggested through the use of conditional value at risk. Results are generated based on simulated data and illustrate the potential of implementing the method at Forsmark. / Tillgångsförvaltning inom kärnkraftsindustrin har blivit alltmer aktuellt i takt med att säkerhetskraven har skärpts och tillförlitlighet i energiproduktionen blivit viktigare. Effektiv tillgångshantering säkerställer prestanda och reliabilitet i ett kärnkraftverk genom att hitta en balans mellan kostnader, möjligheter och risker för att maximera nyttan av tillgångar. Projekturval i tillgångsförvaltningen kan ofta modelleras som ett kapitalbudgeteringsproblem, där investeringar utvärderas utifrån kostnader och uppsida, vilket påvisar en koppling till matematisk optimering. Denna studie behandlar tillgångshantering vid det svenska kärnkraftverket Forsmark och syftar till att implementera en optimeringsmodell för att förbättra projekturvalet relaterat till underhåll av tillgångar vid anläggningen. Det första steget i studien bearbetar den befintliga litteraturen inom området för att få en uppfattning av relevanta metoder. Den mest relevanta metoden identifierades som en mix mellan riskinformerad tillgångsförvaltning och kapitalbudgetering. En metod baserad på de generella principerna för dessa områden utvecklades och anpassades för de specifika förutsättningarna på Forsmark. Flera modeller av olika komplexitet utvecklades och den slutgiltiga stokastiska modellen inkorporerar osäkerhet i de mest relevanta ingångsvariablerna genom att anta sannolikhetsfördelningar. Slutligen föreslås en metod för att implementera ett kvantitativt riskmått i optimeringen genom att använda CVaR. Resultaten genereras utifrån simulerade data och illustrerar potentialen i att implementera metoden på Forsmark.