[pt] Nesta tese são propostos modelos e algoritmos aproximados para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro (AGMD). Este problema modela tipicamente aplicações em projetos de redes de computadores onde todos os vértices devem comunicar-se entre si a um custo mínimo, garantindo um certo nível de serviço. Os modelos propostos por Achuthan e Caccetta para o AGMD são reforçados através da introdução de restrições válidas. Uma relaxação lagrangeana é proposta para o modelo de multifluxo básico de Gouveia e Magnanti. Essa relaxação é utilizada para o desenvolvimento de heurísticas lagrangeanas. Adaptações são realizadas nas heurísticas construtivas propostas por Deo e Abdalla, e por Raidl e Julstrom. São propostas ainda quatro estratégias de busca local, uma heurística do tipo GRASP e outra híbrida. São obtidos limites superiores a menos de 2% do ótimo para as classes de instâncias usadas nos trabalhos de Gouveia e Magnanti, e de Santos, Lucena e Ribeiro. Além disto, obteve-se os melhores resultados conhecidos até o presente momento para 11 instâncias de grafos completos usadas por Raidl, Julstrom e Gruber. / [en] In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber

[pt] Esta tese investiga e desenvolve algoritmos baseados em relaxação Lagrangiana e técnica de desagregação multiparamétrica normalizada para resolver problemas não convexos de programação inteira-mista quadrática com restrições quadráticas. Primeiro, é realizada uma revisão de técnias de relaxação para este tipo de problema e subclasses do mesmo. Num segundo momento, a técnica de desagregação multiparamétrica normalizada é aprimorada para sua versão reformulada onde o tamanho dos subproblemas a serem resolvidos tem seu tamanho reduzido, em particular no número de variáveis binárias geradas. Ademais, dificuldas em aplicar a relaxação Lagrangiana a problemas não convexos são discutidos e como podem ser solucionados caso o subproblema dual seja substituído por uma relaxação não convexa do mesmo. Este método Lagrangiano modificado é comparado com resolvedores globais comerciais e resolvedores de código livre. O método proposto convergiu em 35 das 36 instâncias testadas, enquanto o Baron, um dos resolvedores que obteve os melhores resultados, conseguiu convergir apenas para 4 das 36 instâncias. Adicionalmente, mesmo para a única instância que nosso método não conseguiu resolver, ele obteve um gap relativo de menos de 1 por cento, enquanto o Baron atingiu um gap entre 10 por cento e 30 por cento para a maioria das instâncias que o mesmo não convergiu. / [en] This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming. First, relaxations for quadratic programming and related problem classes are reviewed. Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables. Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations. This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances. The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36. Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1 percent in all instances, while Baron achieved relative gaps between 10 percent and 30 percent in most of them.