%0 Thesis
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3F2PHGS
%@usergroup administrator
%@usergroup camila
%@usergroup cr_seabra@yahoo.com.br
%@usergroup jefferson
%@usergroup viveca@sid.inpe.br
%@usergroup yolanda.souza@mcti.gov.br
%3 publicacao.pdf
%@secondarytype TDI
%2 sid.inpe.br/mtc-m18@80/2009/04.24.16.45.07
%A Almeida Junior, Carlos Renato Seabra,
%P 67
%@dissemination NTRSNASA; BNDEPOSITOLEGAL.
%@group CAP-SPG-INPE-MCT-BR
%K problema da diversidade máxima, geração de colunas, relaxação lagrangeana, método dos subgradientes, particionamento de grafo, otimização combinatória, programação linear, maximun diversity problem, column generation, lagrangean relaxation, sub gradients method, graph partitioning, combinatorial optimizatiom, linear programming.
%@e-mailaddress cr_seabra@yahoo.com.br
%@documentstage not transferred
%J Lagrangean relaxation with clustering division applied to the maximum diversity problem
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%@copyholder SID/SCD
%@secondarykey INPE-15760-TDI/1503
%9 Dissertação (Mestrado em Computação Aplicada)
%@area COMP
%8 2009-04-03
%X O Problema da Diversidade Máxima é um problema de natureza combinatória com o objetivo de selecionar os m itens mais distintos de um conjunto N = {e$ _1$ , e$ _2$ , ..., e$ _n$ }, com emph{n} elementos, tal que emph{m < n} e existe uma medida de diversidade para cada par de elementos. A literatura apresenta a formulação quadrática do problema e sua linearização. A proposta deste trabalho consiste no cálculo de limitantes superiores com base nessa formulação linearizada. A partir da confecção de um grafo modelado para representar o Problema da Diversidade Máxima, esse grafo é particionado em emph{k} clusters e o problema, dividido em emph{k} subproblemas relacionados aos clusters criados. Esses subproblemas são formulados de acordo com a metodologia utilizada. Nesse processo de divisão, algumas restrições são relaxadas no sentido lagrangeano e a solução final apresenta um limitante superior para o problema. Duas técnicas distintas foram utilizadas separadamente neste trabalho, a fim de melhorar esse limitante em processos iterativos: o método dos subgradientes e o da geração de colunas. Embora os esforços tenham sido estritamente direcionados à formulação e à modelagem matemática do problema principal e seus subproblemas, ambos os métodos foram implementados e executados para fim de análise e comparação de resultados. ABSTRACT: The Maximum Diversity Problem is a problem of combinatorial nature with the objective of selecting the m most distinct items from a set N = {e$ _1$ , e$ _2$ , ..., e$ _n$ } with emph{n} elements, such as emph{m < n} and exists a diversity measure for each pair of elements. In literature, we can find the problems quadratic formulation and its linearization. The proposal of this work consists in calculate the upper bounds, based on the linearized formulation. From the confection of a graph modeled to represent the Maximum Diversity Problem, this graph is partitioned into emph{k} clusters and the problem is divided into  emph{k} subproblems related to the created clusters. These subproblems are formulated according to the used methodology. In this division process, some constraints are relaxed in the lagrangean sense and the final solution presents an upper bound for the problem. Two distinct techniques were used separately in this work, with the purpose of improve this bound with iterative processes: the subgradients and the column generation method. Although the efforts have been strictly aimed to the mathematic modeling and formulation of the main problem and its subproblems, both methods were implemented and executed in order to make results comparison and analysis.
%@project CAP-SPG-INPE-MCT-BR
%E Vijaykumar, Nandamudi Lankalapalli (presidente),
%E Lorena, Luiz Antonio Nogueira (orientador),
%E Becceneri, José Carlos,
%E Silva, José Demisio Simões da,
%E Milioni, Armando Zeferino,
%T Relaxação lagrangeana com divisão em clusters aplicada ao problema da diversidade máxima
%4 sid.inpe.br/mtc-m18@80/2009/04.24.16.45
%D 2009
%@mirrorrepository sid.inpe.br/mtc-m18@80/2008/03.17.15.17.24
%C São José dos Campos