<p>Doktorska disertacija se bavi temama rešavanja računarski teških<br />problema kombinatorne optimizacije. Istaknut je problem maksimalne<br />klike kao predstavnik određenih struktura u grafovima. Problem<br />maksimalne klike i sa njim povezani problemi su formulisani kao<br />nelinearne funkcije. Rešavani su sa ciljem otkrivanja novih metoda<br />koje pronalaze dobre aproksimacije rešenja za neko razumno vreme.<br />Predložene su varijante Metode promenljivih okolina na rešavanje<br />maksimalne klike u grafu. Povezani problemi na grafovima se mogu<br />primeniti na pretragu informacija, raspoređivanje, procesiranje<br />signala, teoriju klasifikacije, teoriju kodiranja, itd. Svi algoritmi<br />su implementirani i uspešno testirani na brojnim različitim<br />primerima.</p> / <p>This Ph.D. thesis addresses topics NP hard problem solving approaches in<br />combinatorial optimization and according to that it is highlighted maximum<br />clique problem as a representative of certain structures in graphs. Maximum<br />clique problem and related problems with this have been formulated as non<br />linear functions which have been solved to research for new methods and<br />good solution approximations for some reasonable time. It has been<br />proposed several different extensions of Variable Neighborhood Search<br />method. Related problems on graphs could be applied on information<br />retrieval, scheduling, signal processing, theory of classi_cation, theory of<br />coding, etc. Algorithms are implemented and successfully tested on various<br />different tasks.</p>

Indoor Positioning Systems (IPS) using the existing WLAN have won growing interest in the last years, it can be a perfect supplement to provide location information of users in indoor environments where other positioning techniques such as GPS, are not much effective. The thesis manuscript proposes a new approach to define a WLAN-based indoor positioning system (WLAN-IPS) as a combinatorial optimization problem to guarantee the requested communication quality while optimizing the positioning error. This approach is characterised by several difficult issues we tackled in three steps.At first, we designed a WLAN-IPS and implemented it as a test framework. Using this framework, we looked at the system performance under various experimental constraints. Through these experiments, we went as far as possible in analysing the relationships between the positioning error and the external environmental factors. These relationships were considered as evaluation indicators of the positioning error. Secondly, we proposed a model that defines all major parameters met in the WLAN-IPS from the literature. As the original purpose of the WLAN infrastructures is to provide radio communication access, we introduced an additional purpose which is to minimize the location error within IPS context. Two main indicators were defined in order to evaluate the network Quality of Service (QoS) and the positioning error for Location-Based Service (LBS). Thirdly, after defining the mathematical formulation of the optimisation problem and the key performance indicators, we proposed a mono-objective algorithm and a multi-objective algorithm which are based on Tabu Search metaheuristic to provide good solutions within a reasonable amount of time. The simulations demonstrate that these two algorithms are highly efficient for the indoor positioning optimization problem.

[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.

Cette thèse porte sur le développement de modèles mathématiques et d’algorithmes d’optimisation pour la conception de chaînes logistiques durables. Nous proposons des modèles mono-périodiques, multi-produits et multi-modes de transport à quatre niveaux (fournisseurs, unités de production, entrepôts et clients) couvrant les piliers économique et environnemental du développement durable. Les variables de décision concernent la localisation des sites logistiques intermédiaires (unités de production et entrepôts), les choix de technologie et de mode de transport, et la détermination des flux de produits. Un premier modèle est basé uniquement sur la minimisation des coûts totaux. Ce modèle est étendu au cas bi-objectif en considérant la minimisation des émissions de CO2. Nous proposons une procédure d’optimisation basée sur la recherche à voisinage large (LNS : Large Neighborhood Search). L’application de cette méthode à un problème à variables mixtes tel que la conception de chaîne logistique est inédite. Notre extension au cas bi-objectif fait intervenir l’algorithme récent de recherche locale multi-directionnelle. Les expérimentations numériques permettent d’évaluer la pertinence de nos modèles et de comparer les performances de nos algorithmes à celles d’un solveur du marché. / This thesis focuses on the development of mathematical models and optimization algorithms for the design of sustainable supply chains. We propose single-period, multi-commodity, multi-mode, four level models (suppliers, production facilities, warehouses and customers) covering economic and environmental pillars of sustainable development. The decision variables are related to the location of the intermediate logistics sites (production units and warehouses), the choice of technology and mode of transport, and the determination of product flow. A first model is based solely on minimizing total costs. This model is extended to bi-objective minimization by considering CO2 emissions. We propose an optimization procedure based on the Large Neighborhood Search (LNS) metaheuristic, which had almost never been applied to problems with mixed variables such as design supply chain. Our extension to the bi-objective case involves the use of the multi-directional local search (MDLS). Extensive numerical experiments assess the relevance of our model and compare the performance of our algorithms to those of a state-of-the-art solver.

Orientador: Percival Bueno de Araujo / Resumo: Neste trabalho, uma técnica baseada na Busca em Vizinhança Variável Básica é apresentada para realizar o ajuste coordenado dos parâmetros dos controladores suplementares de amortecimento Thyristor Controlled Series Capacitor - Power Oscillation Damping e Estabilizadores de Sistemas de Potência, a fim de garantir a estabilidade a pequenas perturbações de sistemas elétricos de potência. A estratégia do método de ajuste proposto consiste em explorar sistematicamente estruturas de vizinhança atrelada a uma etapa de busca local, tornando possível a obtenção de soluções ótimas e a manutenção da capacidade de evitar a estagnação em um ótimo local. Um modelo do TCSC por injeção de corrente é apresentado e seus coeficientes de sensibilidade de corrente são deduzidos para incorporação ao Modelo de Sensibilidade de Corrente, que é utilizado para representar o sistema elétrico de potência. Com a inclusão da modelagem dos controladores de amortecimento, simulações são realizadas em dois sistemas testes, conhecidos como sistema Simétrico de Duas Áreas e sistema New England. Os resultados obtidos são analisados para melhor compreensão do comportamento do sistema elétrico de potência quando submetido a uma pequena perturbação e da influência dos controladores de amortecimento neste cenário. Os parâmetros dos controladores são ajustados pelo algoritmo Particle Swarm Optimization, por um Algoritmo Genético e, também, pelo método proposto neste trabalho. Os desempenhos individuais dos métodos d... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work, a technique based on Basic Variable Neighborhood Search is presented to perform the coordinated tuning of the parameters of the supplementary damping controllers Thyristor Controlled Series Capacitor - Power Oscillation Damping and Power System Stabilizers in order to guarantee the small-signal stability of the electric power systems. The strategy of the proposed tuning method consists in systematically exploring neighborhood structures followed by a local search stage, making it possible to obtain optimal solutions and to maintain the ability to avoid stagnation in a local optimum. A current injection model for the TCSC is presented and its current sensitivity coefficients are deduced for incorporation into the Current Sensitivity Model, which is used to represent the electric power system. With the inclusion of the damping controllers modeling, simulations are performed on two test systems, known as the Two-Area Symmetric system and New England system. The results obtained are analyzed to better understand the behavior of the electric power system when subjected to a small disturbance and the influence of the damping controllers in this scenario. The controllers parameters are tuned by the Particle Swarm Optimization algorithm, by a Genetic Algorithm and also by the method proposed in this work. The individual performances of the tuning methods are compared in order to conclude on the technique best suited for this type of problem, including the analysis of a ... (Complete abstract click electronic access below) / Doutor

Les suspensions colloïdales ont été étudiées par simulations numériques à partir de deux modèles : la dynamique Brownienne (BD) et la SRD-MD (Stochastic Rotation Dynamics - Molecular Dynamics). Ces études ont consisté à reprendre des travaux existants pour les porter sur GPU, tout en cherchant différentes optimisations possibles adaptées à ces simulations. Une amélioration de la recherche de voisinage de la littérature a pu être utilisée pour toutes ces simulations de type BD. Une simulation de SRD-MD avec couplage de force qui n'avait pas encore été parallélisée sur GPU dans la littérature, a été implémentée en utilisant un nouveau schéma de décomposition adapté à cette simulation, améliorant considérablement les performances. Ces simulations ont pu donner lieu par la suite à des études sur des suspensions colloïdales plus complexes : une hétéroagrégation entre deux suspensions avec des particules de même taille, une hétéroagrégation entre deux populations de colloïdes de tailles très différentes, et en dehors des suspensions colloïdales, une simulation de nanoalliages. Enfin, le modèle de SRD a été adapté afin d'être utilisé dans le cadre d'animation physique de fluide réaliste dans le contexte de l'informatique graphique. Des adaptations du modèle pour y incorporer des notions comme la gestion de la compressibilité, de la tension de surface ont dues être apportées. Des premiers résultats ont pu permettre de réaliser quelques simulations, dont une chute d'eau dans une verre. / Colloïdal suspensions have been studied by means of numerical simulation, using two physical models : Brownian dynamics and Stochastic Rotation Dynamics - Molecular Dynamics. These studies consist in parallizing colloïdal simulations from previous studies on GPU, and find some new optimisations for these specific simulations. An improvement of the neigborhood search has been implemented in all our BD type simulations. A SRD-MD with force coupling have been implemented for the first time in the literature, using a new decomposition scheme, which improves significantly its performances. Then, theses simulations have been adapted to study more complex colloidal suspensions : an interfacial heteroaggregation of colloidal suspensions, a heteroaggregation between two types of particles with a large size ratio, and outside this context, a nanoalloy simulation. Finally, the SRD model has been adapted to realistic fluid animtion from computer science context. Theses adaptations require to add to SRD model, the notion of compressibility and surface tension. First results have been released, like a pouring water into a glass simulation.

Made available in DSpace on 2015-05-14T12:36:37Z (GMT). No. of bitstreams: 1 ArquivoTotalDaniel.pdf: 2752447 bytes, checksum: 5dbeb5dd6c935f25f004b1edb1df7d70 (MD5) Previous issue date: 2013-03-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Problems of traffic jam, lack of vacancies in garages and cars underutilized are part of the current scenario of big cities. In this work is created a module for creating efficient routes for a system using the approach Dial-a-Ride Problem. The DARP is a vehicle routing problem that belongs to NP-complete class. It aims is to minimize operating costs while maintaining quality of service to the client. It is presented an algorithm that uses the metaheuristics Iterated Local Search with the Variable Neighborhood Search to solve the DARP. Compared to related work in the area, the results were better regarding to distance traveled and average travel time of customers. / Problemas de congestionamentos, falta de vagas em garagens e carros subutilizados fazem parte do cenário atual das grandes cidades. Neste trabalho é criado um módulo para criação de rotas eficiente para sistemas de caronas utilizando a abordagem Dial-a-Ride Problem. O DARP é um problema de roteamento pertencente a classe NP-Completo. Este tem como objetivo minimizar os custos operacionais, mas mantendo uma qualidade de serviço para o usuário. É apresentado um algoritmo que utiliza as metaheurística Iterated Local Search juntamente com a Variable Neighborhood Search para solucionar o DARP. Comparados com outros trabalhos relevantes na área, os resultados encontrados foram melhores no que se refere à distância percorrida e no tempo médio de viagem dos clientes.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:47:47Z No. of bitstreams: 1 AllysonFernandesDaCostaSilva_DISSERT.pdf: 1659813 bytes, checksum: 0de7287ef5c2c4ae621833638c04aa5f (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-08T00:21:06Z (GMT) No. of bitstreams: 1 AllysonFernandesDaCostaSilva_DISSERT.pdf: 1659813 bytes, checksum: 0de7287ef5c2c4ae621833638c04aa5f (MD5) / Made available in DSpace on 2017-11-08T00:21:06Z (GMT). No. of bitstreams: 1 AllysonFernandesDaCostaSilva_DISSERT.pdf: 1659813 bytes, checksum: 0de7287ef5c2c4ae621833638c04aa5f (MD5) Previous issue date: 2017-06-30 / Problemas de localiza??o buscam determinar as melhores posi??es onde devem ser instaladas facilidades de modo a atender demandas existentes. Pela vasta aplicabilidade da ?rea, diversas caracter?sticas j? foram importadas aos modelos para melhor representar situa??es pr?ticas. Uma delas generaliza os modelos cl?ssicos para situa??es em que decis?es de localiza??o devem ser tomadas periodicamente. Outra, permite que modelos tratem do dimensionamento das capacidades como uma vari?vel do problema. O Problema Din?mico de Localiza??o de Facilidades com Capacidades Modulares unifica estas e outras caracter?sticas presentes em problemas de localiza??o num ?nico e generalizado modelo. Este problema foi recentemente formulado na literatura, onde uma abordagem exata foi introduzida e aplicada a inst?ncias derivadas de um estudo de caso no contexto da explora??o de recursos florestais. Neste trabalho ser? apresentado um m?todo alternativo para resolver o mesmo problema. O m?todo escolhido utiliza a estrutura da metaheur?stica Algoritmo Gen?tico e a hibridiza com uma rotina de Descida em Vizinhan?a Vari?vel com tr?s vizinhan?as de busca adaptadas de vizinhan?as aplicadas a outros problemas de localiza??o. Experimentos atestaram a efetividade da metaheur?stica h?brida desenvolvida em compara??o ? aplica??o dos m?todos puros. Na compara??o com o m?todo exato, a heur?stica se mostrou competente ao chegar a solu??es at? 0,02% de dist?ncia do ?timo na maioria das inst?ncias testadas. / Location problems aim to determine the best positions where facilities should be installed in order to meet existing demands. Due to its wide applicability, several characteristics have already been appended to the models to better represent real situations. One of them generalizes classical models to the case that location decisions should be taken periodically. Another allows models to deal with capacity sizing as a problem variable. The Dynamic Facility Location Problem with Modular Capacities unifies these and other characteristics present in location problems in a single and generalized model. This problem was recently formulated in literature where an exact approach was introduced and applied to instances of a case study in the context of the forestry sector. We present an alternative method to solve the same problem. The method chosen uses a Genetic Algorithm metaheuristic framework and hybridizes it with a Variable Neighborhood Descent routine with three neighborhoods adapted from others applied to location problems. Experiments attested the effectiveness of the hybrid metaheuristic developed in comparison to the use of those methods purely. Compared to the exact approach, the heuristic proved to be competent by finding solutions up to a gap of 0,02% to the global optimum in the majority of the instances tested.

This thesis aims to see If an algorithm could automatically generate a meal plan that is optimized for low food waste. Design and creation is the method used and the algorithm is developed over a few iterations. The idea is that the algorithm could be used in a mobile application that allows users to search for recipes, mark the ones they like, add their own, and generate a meal plan. The resulting algorithm consists of four parts; an input stage, a stage that decides when to cook each portion, an improvement stage in which the algorithm searches for a better combination of recipes, and an output stage. An adaptation of a neighborhood search is used for the search algorithm, in addition, two heuristic evaluation functions are used to evaluate the waste and other factors of the meal plan. The test results show that the algorithm can generate meal plans with no leftover items (that last shorter than 60 days) for a lot of different test cases. More recipes produce better results up to a certain point, but not so many recipes are needed to have a chance of a successful meal plan generation. Future testing and research in this area could lead to a lot of benefits for people and the climate.

No description available.