| 1. Identity statement | ||||||||||||||||
| Reference Type | Thesis or Dissertation (Thesis) | |||||||||||||||
| Site | mtc-m16c.sid.inpe.br | |||||||||||||||
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S | |||||||||||||||
| Identifier | 8JMKD3MGP8W/357DP4B | |||||||||||||||
| Repository | sid.inpe.br/mtc-m18@80/2009/04.24.16.45 (restricted access) | |||||||||||||||
| Last Update | 2010:05.12.17.33.31 (UTC) sergio | |||||||||||||||
| Metadata Repository | sid.inpe.br/mtc-m18@80/2009/04.24.16.45.07 | |||||||||||||||
| Metadata Last Update | 2020:04.28.17.48.36 (UTC) administrator | |||||||||||||||
| Secondary Key | INPE-15760-TDI/1503 | |||||||||||||||
| Citation Key | AlmeidaJr:2009:ReLaDi | |||||||||||||||
| Title | Relaxação lagrangeana com divisão em clusters aplicada ao problema da diversidade máxima  | |||||||||||||||
| Alternate Title | Lagrangean relaxation with clustering division applied to the maximum diversity problem | |||||||||||||||
| Course | CAP-SPG-INPE-MCT-BR | |||||||||||||||
| Year | 2009 | |||||||||||||||
| Date | 2009-04-03 | |||||||||||||||
| Access Date | 2024, Apr. 26 | |||||||||||||||
| Thesis Type | Dissertação (Mestrado em Computação Aplicada) | |||||||||||||||
| Secondary Type | TDI | |||||||||||||||
| Number of Pages | 67 | |||||||||||||||
| Number of Files | 1 | |||||||||||||||
| Size | 472 KiB | |||||||||||||||
| 2. Context | ||||||||||||||||
| Author | Almeida Junior, Carlos Renato Seabra | |||||||||||||||
| Group | CAP-SPG-INPE-MCT-BR | |||||||||||||||
| Committee | Vijaykumar, Nandamudi Lankalapalli (presidente) Lorena, Luiz Antonio Nogueira (orientador) Becceneri, José Carlos Silva, José Demisio Simões da Milioni, Armando Zeferino | |||||||||||||||
| e-Mail Address | cr_seabra@yahoo.com.br | |||||||||||||||
| University | Instituto Nacional de Pesquisas Espaciais (INPE) | |||||||||||||||
| City | São José dos Campos | |||||||||||||||
| History (UTC) | 2009-04-24 16:45:07 :: cr_seabra@yahoo.com.br -> yolanda :: 2009-05-19 19:20:13 :: yolanda -> cr_seabra@yahoo.com.br :: 2009-05-20 19:55:13 :: cr_seabra@yahoo.com.br -> yolanda :: 2009-05-21 20:03:26 :: yolanda -> supervisor :: 2009-05-26 13:33:46 :: supervisor -> yolanda :: 2009-05-26 13:52:36 :: yolanda -> supervisor :: 2009-07-03 15:08:33 :: supervisor -> cr_seabra@yahoo.com.br :: 2009-07-03 16:42:39 :: cr_seabra@yahoo.com.br -> administrator :: 2009-07-07 16:15:27 :: administrator -> yolanda :: 2010-02-05 14:59:54 :: yolanda -> camila :: 2010-02-05 16:12:07 :: camila -> viveca@sid.inpe.br :: 2010-02-05 21:53:41 :: viveca@sid.inpe.br -> camila :: 2010-03-08 17:07:05 :: camila -> ricardo :: 2010-05-12 15:20:44 :: ricardo -> viveca@sid.inpe.br :: 2010-05-12 17:35:25 :: viveca@sid.inpe.br -> administrator :: 2018-11-01 13:26:43 :: administrator -> sergio :: 2009 2019-04-25 16:49:31 :: sergio -> administrator :: 2009 2020-04-28 17:48:36 :: administrator -> simone :: 2009 | |||||||||||||||
| 3. Content and structure | ||||||||||||||||
| Is the master or a copy? | is the master | |||||||||||||||
| Content Stage | completed | |||||||||||||||
| Transferable | 1 | |||||||||||||||
| Keywords | 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 | |||||||||||||||
| Abstract | 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. | |||||||||||||||
| Area | COMP | |||||||||||||||
| Arrangement | urlib.net > BDMCI > Fonds > Produção pgr ATUAIS > CAP > Relaxação lagrangeana com... | |||||||||||||||
| doc Directory Content | access | |||||||||||||||
| source Directory Content |
| |||||||||||||||
| agreement Directory Content | there are no files | |||||||||||||||
| 4. Conditions of access and use | ||||||||||||||||
| Language | pt | |||||||||||||||
| Target File | publicacao.pdf | |||||||||||||||
| User Group | administrator camila cr_seabra@yahoo.com.br jefferson viveca@sid.inpe.br yolanda.souza@mcti.gov.br | |||||||||||||||
| Visibility | shown | |||||||||||||||
| Copy Holder | SID/SCD | |||||||||||||||
| Read Permission | deny from all and allow from 150.163 | |||||||||||||||
| Update Permission | not transferred | |||||||||||||||
| 5. Allied materials | ||||||||||||||||
| Mirror Repository | sid.inpe.br/mtc-m18@80/2008/03.17.15.17.24 | |||||||||||||||
| Next Higher Units | 8JMKD3MGPCW/3F2PHGS | |||||||||||||||
| Dissemination | NTRSNASA; BNDEPOSITOLEGAL. | |||||||||||||||
| Host Collection | sid.inpe.br/mtc-m18@80/2008/03.17.15.17 | |||||||||||||||
| 6. Notes | ||||||||||||||||
| Empty Fields | academicdepartment affiliation archivingpolicy archivist callnumber contenttype copyright creatorhistory descriptionlevel doi electronicmailaddress format isbn issn label lineage mark nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup resumeid rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype url versiontype | |||||||||||||||
| 7. Description control | ||||||||||||||||
| e-Mail (login) | simone | |||||||||||||||
| update | ||||||||||||||||