The Diameter-Constrained Minimum Spanning Tree Problem seeks a least cost spanning tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20-node and 100-edge problem after one week of computation. We formulate the problem as a directed tree from a selected central node or a selected central edge. Our model simultaneously finds a central node or a central edge and uses it as the source for the commodities in a directed multicommodity flow model with hop constraints. The new model has been able to solve the 20-node, 100-edge instance to optimality after less than four seconds. We also present model enhancements when the diameter bound is odd (these situations are more difficult). We show that the linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially-solvable cases of the problem. We also examine the Diameter Constrained Minimum Steiner Tree problem. We present computational experience in solving problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints.

Surveillance is an important application for unmanned aerial vehicles (UAVs). The sensed information often has high priority and it must be made available to human operators as quickly as possible. Due to obstacles and limited communication range, it is not always possible to transmit the information directly to the base station. In this case, other UAVs can form a relay chain between the surveillance UAV and the base station. Determining suitable positions for such UAVs is a complex optimization problem in and of itself, and is made even more difficult by communication and surveillance constraints. To solve different variations of finding positions for UAVs for surveillance of one target, two new algorithms have been developed. One of the algorithms is developed especially for finding a set of relay chains offering different trade-offs between the number of UAVsand the quality of the chain. The other algorithm is tailored towards finding the highest quality chain possible, given a limited number of available UAVs. Finding the optimal positions for surveillance of several targets is more difficult. A study has been performed, in order to determine how the problems of interest can besolved. It turns out that very few of the existing algorithms can be used due to the characteristics of our specific problem. For this reason, an algorithm for quickly calculating positions for surveillance of multiple targets has been developed. This enables calculation of an initial chain that is immediately made available to the user, and the chain is then incrementally optimized according to the user’s desire.

Random graph processes are most often used to investigate theoretical questions about random graphs. A randomised algorithm can be defined specifically for the purpose of finding some structure in a graph, such as a matching, a colouring or a particular kind of sub graph. Properties of the related random graph process then suggest properties, or bounds on properties, of the structure. In this thesis, we use a random graph process to analyse a particular load balancing algorithm from theoretical computer science. By doing so, we demonstrate that random graph processes may also be used to analyse other algorithms and systems of a random nature, from areas such as computer science, telecommunications and other areas of engineering and mathematics. Moreover, this approach can lead to theoretical results on the performance of algorithms that are difficult to obtain by other methods. In the course of our analysis we are also led to some results of the first kind, relating to the structure of the random graph. / The particular algorithm that we analyse is a randomised algorithm for an off-line load balancing problem with two choices. The load balancing algorithm, in an initial stage, mirrors an algorithm which finds the k-core of a graph. This latter algorithm and the related random graph process have been previously analysed by Pittel, Spencer and Wormald, using a differential equation method, to determine the thresholds for the existence of a k-core in a random graph. We modify their approach by using a random pseudograph model due to Bollobas and Frieze, and Chvatal, in place of the uniform random graph. This makes the analysis somewhat simpler, and leads to a shortened derivation of the thresholds and other properties of k-cores.(For complete abstract open document)

Made available in DSpace on 2015-05-14T12:36:55Z (GMT). No. of bitstreams: 1 parte1.pdf: 1169586 bytes, checksum: 685986454ee5e2cc58d709e7d646732f (MD5) Previous issue date: 2009-08-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a new heuristic, called Heurística 1, and the implementations of the GRASP, Simulated Annealing and Genetic Algorithms metaheuristics for the rectilinear Steiner minimum tree problem (RSMTP), talking about its theoretical aspects, like computational complexity, and practical ones, like pseudo-codes and implementation strategies. The new techniques for RSMTP presented, especially the Genetic Algorithms, have computational results of superior quality in comparison to the best heuristics in present litera / Este trabalho apresenta uma nova heurística, denominada Heurística 1, e a implementação das metaheurísticas GRASP, Simulated Annealing e Algoritmos Genéticos para o problema da árvore retilínea mínima de Steiner (RSMTP), discorrendo sobre seus aspectos teóricos, como a complexidade computacional; e práticos, como pseudocódigos e estratégias de implementação. As novas abordagens para o RSMTP apresentadas, em especial os Algoritmos Genéticos, ostentam resultados computacionais de qualidade superior às apresentadas pelas melhores heurísticas da literatura atual.