In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)

Submitted by Felipe Rodrigues de Menezes Tomaz (felipetomaz@gmail.com) on 2017-03-08T18:07:35Z No. of bitstreams: 1 Dissertação - Final.pdf: 1323190 bytes, checksum: c28bd29047e066ff34bb9203c46e9fec (MD5) / Rejected by Renata de Souza Nascimento (renata.souza@fgv.br), reason: Felipe, boa noite Por gentileza, realizar as seguintes alterações para que possamos aceitar seu trabalho: Retirar a acentuação do nome Getúlio Centralizar os títulos: Dedicatória, Resumo e Abstract. O título está diferente com o que consta em Ata e nenhuma solicitação do orientador. Neste caso, iremos entrar em contato para que o mesmo confirme a alteração. Em seguida, deverá submeter o arquivo novamente. Att on 2017-03-08T23:14:39Z (GMT) / Submitted by Felipe Rodrigues de Menezes Tomaz (felipetomaz@gmail.com) on 2017-03-09T12:57:43Z No. of bitstreams: 1 Dissertação - Final.pdf: 1323164 bytes, checksum: 26add34e2f577cfcec02f52da04b7845 (MD5) / Rejected by Renata de Souza Nascimento (renata.souza@fgv.br), reason: Felipe, boa tarde Em contato com o prof. Ricardo Rochman, o mesmo confirma que não solicitou e não autoriza a mudança no título do trabalho. Deverá retornar ao título que consta em Ata e protocolo inicial: ESTUDO DE UTILIZAÇÃO DE UMA MINIMUM SPANNING TREE DE CORRELAÇÕES COMO SELETORA DE AÇÕES EM UMA ESTRATÉGIA DE COINTEGRAÇÃO NO MERCADO DE BRASILEIRO Att. on 2017-03-09T16:15:49Z (GMT) / Submitted by Felipe Rodrigues de Menezes Tomaz (felipetomaz@gmail.com) on 2017-03-09T19:35:28Z No. of bitstreams: 1 Dissertação - Final.pdf: 1322284 bytes, checksum: 9ec2cbcae5a0293ac6a12c5a9ae85ebf (MD5) / Approved for entry into archive by Renata de Souza Nascimento (renata.souza@fgv.br) on 2017-03-09T19:40:49Z (GMT) No. of bitstreams: 1 Dissertação - Final.pdf: 1322284 bytes, checksum: 9ec2cbcae5a0293ac6a12c5a9ae85ebf (MD5) / Made available in DSpace on 2017-03-10T13:02:47Z (GMT). No. of bitstreams: 1 Dissertação - Final.pdf: 1322284 bytes, checksum: 9ec2cbcae5a0293ac6a12c5a9ae85ebf (MD5) Previous issue date: 2017-02-10 / This work aimed to evaluate the possibility of using a miminum spanning tree (MST) of correlation between assets as a selection tool in a pairs trading strategy based on cointegration. From a selection of Bovespa exchange index assets, cointegration tests were performed between pairs of assets and, subsequently, starting from positive results, backtestings were executed. After that, the backtestings were filtered by information included in an MST. For a given period, when a cointegration was found between a pair of assets, a MST was developed and it was analyzed if there was a direct link between those assets in the MST’s structure. Otherwise, the backtesting result from the cointegration would be disregarded. By comparing the total set of results with the subset of results that took into account the MST constraint, it was evaluated the impact of the use of the MST, as an asset selector, on the result of the pairs trading strategy. / Essa dissertação teve como objetivo avaliar a possibilidade de utilização de uma miminum spanning tree (MST) de correlação entre ativos como instrumento de seleção em uma estratégia de pairs trading que teve como base a cointegração. A partir de uma seleção de ativos do índice Bovespa, foram feitos testes de cointegração entre pares de ativos e, posteriormente, partindo de resultados positivos, foram executados backtestings que foram filtrados por informações provenientes de uma MST. Para determinado período, ao se encontrar uma cointegração entre um par dos ativos considerados, uma MST foi desenvolvida e analisou-se a existência de um link direto entre o par de ativos na estrutura da MST. Caso contrário, o resultado do backtesting proveniente desta cointegração foi desconsiderado. Fazendo-se a comparação do conjunto total de resultados com o subconjunto de resultados que levam em consideração a restrição da MST, avaliou-se o impacto da utilização da MST, como seletora de ativos, no resultado da estratégia de pairs trading.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The generalized minimum spanning tree problem is present in several situations of the real world, such as in the context of the telecommunications, transports and grouping of data, where a net of necessary clusters to be connected using a node of each cluster. In that work it is presented the project and the implementation of an algorithm of tabu search with path relinking and iterated local search for the generalized minimum spanning tree problem and your variant with at least one vertex by group. In the computational tests 271 instances of TSPLIB were used generated through the grouping methods Center Clustering and Grid Clustering, and more 20 instances for the extension of the problem with at least one vertex by group. The results demonstrate the efficiency of the algorithm proposed in the obtaining of satisfactory solutions for the two problems. / O problema da árvore geradora mínima generalizado está presente em várias situações do mundo real, tais como no contexto das telecomunicações, transportes e agrupamento de dados, nas quais uma rede de grupos precisa ser conectada utilizando um nodo de cada grupo. Nesse trabalho é apresentado o projeto e a implementação de um algoritmo de busca tabu com reconexão de caminhos e busca local iterativa para o problema da árvore geradora mínima generalizado e sua variante com pelo menos um vértice por grupo. Nos testes computacionais foram utilizadas 271 instâncias da TSPLIB geradas através dos métodos de agrupamento Center Clustering e Grid Clustering, e mais 20 instâncias para a extensão do problema com pelo menos um vértice por grupo. Os resultados demonstram a eficiência do algoritmo proposto na obtenção de soluções satisfatórias para os dois problemas.

Neste trabalho foi analisada a influência de um evento sobre o mercado de ações brasileiro a partir das redes, e suas árvores geradoras mínimas, obtidas de medidas de dependência baseadas nas correlações de Pearson, de Spearman e de Kendall. O evento considerado foi a notícia da noite de 17 de maio de 2017 em que o dono da empresa brasileira JBS, Joesley Batista, gravou o então Presidente da República Michel Temer autorizando a compra do silêncio de um Deputado Federal. O dia seguinte a notícia, 18 de maio de 2017, foi definido como o dia do evento. Foram coletados dados de alta frequência de 58 ações do Ibovespa no período de 11 a 25 de maio de 2017. As alterações nas redes das ações do mercado foram analisadas comparando-se o período anterior e posterior ao evento em duas escalas de tempo: (1) Redes diárias: cinco pregões antes do evento, o dia do evento e, cinco pregões depois do evento, com cotações a cada 15 minutos; (2) Agrupadas em antes e depois: agrupando os dados dos 5 dias antes e dos 5 dias depois do evento. O estudo das redes diárias indicou mudança de tendência nas suas propriedades no decorrer do período que contém o evento, com cotações a cada 15 minutos. Isto sugeriu que análise do efeito médio contido nos dados agrupados antes de depois do evento poderiam tornar mais evidente as mudanças na estrutura de rede das ações. As redes antes e depois do evento apresentaram mudanças significativas nas suas métricas que ficaram mais evidenciadas nas árvores geradoras mínimas. As redes geradas pelas correlações de Kendall e Spearman apresentaram um número maior de agrupamentos antes e depois do evento e, após o evento, as árvores geradoras mínimas apresentaram uma redução do número de agrupamentos de ações para todos os tipos de correlação. As distribuições de grau ponderado após o evento indicam uma probabilidade maior de vértices com graus distante da média. As métricas das árvores geradoras mínimas por correlação de Spearman sofreram a maior variação, seguidas pelas de Kendall e Pearson, e também, indicaram que as redes após o evento ficaram mais robustas, ou seja, mais rígidas. A maior robustez das redes após o evento indica maior conectividade do mercado, tornando-o, como um todo, mais suscetível ao impacto de novos acontecimentos. / In this work the influence of an event on the Brazilian stock market was analyzed from networks and its minimum spanning trees obtained from measures of dependence based on the Pearson, Spearman, and Kendall\'s correlations. The event considered was the news in the evening of May 17, 2017 in which the owner of the Brazilian company JBS, Joesley Batista, recorded the Brazilian President Michel Temer authorizing the purchase of the silence of a congress member. The day just after the news, May 18, 2017, was defined as the event day. High-frequency data from 58 Ibovespa shares were collected from 11 to 25 May 2017. Changes in the stocks networks were analyzed comparing the period before and after the event in two time scales: (1) Daily networks: five trade sections before the event, the day of the event and, five trade sections after the event, with price every 15 minutes; (2) Grouped before and after do evento: grouping data from 5 days before and 5 days after event. The study of the daily networks indicated a change of trend in their properties during the period that contains the event, with quotations every 15 minutes. The study of daily networks indicated a change of trend in their properties during the period containing the event. This suggested that analysis of the mean effect of grouped data before and after the event could highlight the changes in the network structure. The networks before and after the event showed significant changes in their metrics, which became more evident from the minimum spanning trees. After the event, the minimum spanning trees for grouped data got a smaller number of clusters in the networks for all kind of correlations. The networks generated by Kendall and Spearman correlations presented a larger number of clusters before and after the event. The weighted degree distributions after the event suggest a power law decay tail for all the correlations considered and indicates a higher probability of vertices with weighted degrees far away from the mean weighted degree. The minimum spanning tree metrics generated by Spearman correlation suffered the greatest variation, followed by those of Kendall and Pearson; and their values indicates that after the event the networks became more robust, that is, more rigid. The increase in the networks robustness after the event indicates a higher market connectivity, making it as a whole, more susceptible to the impact of new events.

Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointe. / In this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search and distributed dynamic linked list, to address the BCP. Based on the BCP solution, a divide and conquer parallel algorithm is implemented for building EMSF and EMST totally on GPU side. The TSP is addressed with different parallel 2-opt local search algorithms, in which we propose a ``multiple K-opt evaluation, multiple K-opt moves" methodology in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour for many edges. This methodology is explained in details to show how we obtain high performance computing both on GPU and CPU side. We test the proposed solutions and report experimental comparison results against the state-of-the-art algorithms.

我們從計算股價的相關矩陣，然後利用隨機矩陣定理的結果，了解到股票市場並非符合隨機過程的預測，進而得知股票對股票之間具有關聯性，然其長時距下股票價格對數報酬的變化會呈現隨機行走的模式，因此我們對其結果提出二種不同的耦合隨機行走模型，試圖闡釋股票市場間的關聯性可融合到耦合隨機行走模型之中，並藉由均方對數報酬(mean square log-return，MSLR)來探討此事情。 最後，為了瞭解關聯性的關係，並利用其來了解股票市場內部結構的特性，因此我們利用股價的相關矩陣來建構最小展開樹進行分析，發現當時間尺度越大其圖形越密集，中心幾乎為「GE」這家公司，因此其股票市場具有一定的判斷指標。 / By means of calculating the correlation matrix of the price of stock and using the results of random matrix theorems，we learned that the stock market does not match the prediction of stochastic processes and the stock-stock is correlated。However，stock’s price log-return changes under long time scale will appear random walk model. Therefore，we propose two kinds of the different coupled random walk model，that try to explain the correlation between the stock markets can be integrated into the coupled random walk model，and using the mean square log-return( MSLR) to investigate this issue。 Finally，to understand the relationship of correlation matrix and by using it to know the characteristics of the underlying structure of the stock market，we use the correlation matrix of the price to construct the minimum spanning tree for analysis。The results showed that when the time scale is greater, the graphics are more intensive，and the center is almost the same company，"GE"， indicating that the stock market has a certain judgment index。

Made available in DSpace on 2014-12-17T15:47:45Z (GMT). No. of bitstreams: 1 GivanaldoRS.pdf: 1524067 bytes, checksum: d73e18e4ae3a0bffab7711efc808bffa (MD5) Previous issue date: 2006-05-19 / Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches / Os problemas de otimiza??o combinat?ria t?m como objetivo maximizar ou minimizar uma fun??o definida sobre um certo dom?nio finito. J? as metaheur?sticas s?o procedimentos destinados a encontrar uma boa solu??o, eventualmente a ?tima, consistindo na aplica??o de uma heur?stica subordinada, a qual tem que ser modelada para cada problema espec?fico. Este trabalho apresenta algoritmos baseados na t?cnica de otimiza??o por nuvem de part?culas (metaheur?stica) para dois problemas de otimiza??o combinat?ria: o Problema do Caixeiro Viajante e o Problema da ?rvore Geradora M?nima Restrita em Grau Multicrit?rio. O primeiro ? um problema em que apenas um objetivo ? otimizado, enquanto o segundo ? um problema que deve lidar com m?ltiplos objetivos. Os algoritmos propostos s?o comparados a outras abordagens para o mesmo problema em quest?o, em termos de qualidade de solu??o, a fim de verificar a efici?ncia desses algoritmos

A propriedade de auto-cura, em redes inteligente de distribuição de energia elétrica, consiste em encontrar uma proposta de reconfiguração do sistema de distribuição com o objetivo de recuperar parcial ou totalmente o fornecimento de energia aos clientes da rede, na ocorrência de uma falha na rede que comprometa o fornecimento. A busca por uma solução satisfatória é um problema combinacional cuja complexidade está ligada ao tamanho da rede. Um método de busca exaustiva se torna um processo muito demorado e muitas vezes computacionalmente inviável. Para superar essa dificuldade, pode-se basear nas técnicas de geração de árvores de extensão mínima do grafo, representando a rede de distribuição. Porém, a maioria dos estudos encontrados nesta área são implementações centralizadas, onde proposta de reconfiguração é obtida por um sistema de supervisão central. Nesta dissertação, propõe-se uma implementação distribuída, onde cada chave da rede colabora na elaboração da proposta de reconfiguração. A solução descentralizada busca uma redução no tempo de reconfiguração da rede em caso de falhas simples ou múltiplas, aumentando assim a inteligência da rede. Para isso, o algoritmo distribuído GHS é utilizado como base na elaboração de uma solução de auto-cura a ser embarcada nos elementos processadores que compõem as chaves de comutação das linhas da rede inteligente de distribuição. A solução proposta é implementada utilizando robôs como unidades de processamento que se comunicam via uma mesma rede, constituindo assim um ambiente de processamento distribuído. Os diferentes estudos de casos testados mostram que, para redes inteligentes de distribuição compostas por um único alimentador, a solução proposta obteve sucesso na reconfiguração da rede, indiferentemente do número de falhas simultâneas. Na implementação proposta, o tempo de reconfiguração da rede não depende do número de linhas nela incluídas. A implementação apresentou resultados de custo de comunicação e tempo dentro dos limites teóricos estabelecidos pelo algoritmo GHS. / The characteristic of self-healing, in smart grids, consists of finding a proposal for a reconfiguration of distribution system aiming at restoring the power, partially or completely to supply the network clients, in the event of network failure, which compromises the energy supply. The search for a satisfactory solution is a combinatorial problem whose complexity is proportional to the network size. An exhaustive search-based method is a time-consuming process and often computationally not viable. To overcome this difficulty, techniques for generating minimal spanning trees of the graph, which represents the smart grid, are exploited. However, the majority of studies in this area provide centralized implementations, where the solution for reconfiguration is achieved by a central control system. In this dissertation, we propose a distributed implementation, where each of the network switch collaborates in the development of the solution for reconfiguration. The proposed decentralized solution seeks a reduction in terms of the network reconfiguration time, in case of a single or multiple failures, thus increasing network intelligence. In this purpose, the GHS distributed algorithm is used as a basis for developing a self-healing solution to be embedded in the processing elements that are included within the line commutation switches of smart grid. The proposed solution is implemented using robots as processing units, which communicate via the same network, thereby creating a distributed processing environment. The several tested case studies show that, for smart grids that to have a single distribution feeder, the proposed solution allowed for a successful reconfiguration of the network, regardless of the number of simultaneous failures. In the proposed implementation, the network reconfiguration time does not depend on the number of buses and lines included. The implementation presents results of communication cost and time within the theoretical bounds of the GHS algorithm.

A propriedade de auto-cura, em redes inteligente de distribuição de energia elétrica, consiste em encontrar uma proposta de reconfiguração do sistema de distribuição com o objetivo de recuperar parcial ou totalmente o fornecimento de energia aos clientes da rede, na ocorrência de uma falha na rede que comprometa o fornecimento. A busca por uma solução satisfatória é um problema combinacional cuja complexidade está ligada ao tamanho da rede. Um método de busca exaustiva se torna um processo muito demorado e muitas vezes computacionalmente inviável. Para superar essa dificuldade, pode-se basear nas técnicas de geração de árvores de extensão mínima do grafo, representando a rede de distribuição. Porém, a maioria dos estudos encontrados nesta área são implementações centralizadas, onde proposta de reconfiguração é obtida por um sistema de supervisão central. Nesta dissertação, propõe-se uma implementação distribuída, onde cada chave da rede colabora na elaboração da proposta de reconfiguração. A solução descentralizada busca uma redução no tempo de reconfiguração da rede em caso de falhas simples ou múltiplas, aumentando assim a inteligência da rede. Para isso, o algoritmo distribuído GHS é utilizado como base na elaboração de uma solução de auto-cura a ser embarcada nos elementos processadores que compõem as chaves de comutação das linhas da rede inteligente de distribuição. A solução proposta é implementada utilizando robôs como unidades de processamento que se comunicam via uma mesma rede, constituindo assim um ambiente de processamento distribuído. Os diferentes estudos de casos testados mostram que, para redes inteligentes de distribuição compostas por um único alimentador, a solução proposta obteve sucesso na reconfiguração da rede, indiferentemente do número de falhas simultâneas. Na implementação proposta, o tempo de reconfiguração da rede não depende do número de linhas nela incluídas. A implementação apresentou resultados de custo de comunicação e tempo dentro dos limites teóricos estabelecidos pelo algoritmo GHS. / The characteristic of self-healing, in smart grids, consists of finding a proposal for a reconfiguration of distribution system aiming at restoring the power, partially or completely to supply the network clients, in the event of network failure, which compromises the energy supply. The search for a satisfactory solution is a combinatorial problem whose complexity is proportional to the network size. An exhaustive search-based method is a time-consuming process and often computationally not viable. To overcome this difficulty, techniques for generating minimal spanning trees of the graph, which represents the smart grid, are exploited. However, the majority of studies in this area provide centralized implementations, where the solution for reconfiguration is achieved by a central control system. In this dissertation, we propose a distributed implementation, where each of the network switch collaborates in the development of the solution for reconfiguration. The proposed decentralized solution seeks a reduction in terms of the network reconfiguration time, in case of a single or multiple failures, thus increasing network intelligence. In this purpose, the GHS distributed algorithm is used as a basis for developing a self-healing solution to be embedded in the processing elements that are included within the line commutation switches of smart grid. The proposed solution is implemented using robots as processing units, which communicate via the same network, thereby creating a distributed processing environment. The several tested case studies show that, for smart grids that to have a single distribution feeder, the proposed solution allowed for a successful reconfiguration of the network, regardless of the number of simultaneous failures. In the proposed implementation, the network reconfiguration time does not depend on the number of buses and lines included. The implementation presents results of communication cost and time within the theoretical bounds of the GHS algorithm.

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.