Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T03:28:44Z (GMT). No. of bitstreams: 1 Oliveira_SaulloHaniellGalvaode_M.pdf: 1171322 bytes, checksum: 5488cfc9b843dbab6d7a5745af1e3d4b (MD5) Previous issue date: 2015 / Resumo: Biclusterização envolve a clusterização simultânea de objetos e seus atributos, definindo mo- delos locais de relacionamento entre os objetos e seus atributos. Assim como a clusterização, a biclusterização tem uma vasta gama de aplicações, desde suporte a sistemas de recomendação, até análise de dados de expressão gênica. Inicialmente, diversas heurísticas foram propostas para encontrar biclusters numa base de dados numérica. No entanto, tais heurísticas apresen- tam alguns inconvenientes, como não encontrar biclusters relevantes na base de dados e não maximizar o volume dos biclusters encontrados. Algoritmos enumerativos são uma proposta recente, especialmente no caso de bases numéricas, cuja solução é um conjunto de biclusters maximais e não redundantes. Contudo, a habilidade de enumerar biclusters trouxe mais um cenário desafiador: em bases de dados ruidosas, cada bicluster original se fragmenta em vá- rios outros biclusters com alto nível de sobreposição, o que impede uma análise direta dos resultados obtidos. Essa fragmentação irá ocorrer independente da definição escolhida de co- erência interna no bicluster, sendo mais relacionada com o próprio nível de ruído. Buscando reverter essa fragmentação, nesse trabalho propomos duas formas de agregação de biclusters a partir de resultados que apresentem alto grau de sobreposição: uma baseada na clusteriza- ção hierárquica com single linkage, e outra explorando diretamente a taxa de sobreposição dos biclusters. Em seguida, um passo de poda é executado para remover objetos ou atributos indesejados que podem ter sido incluídos como resultado da agregação. As duas propostas foram comparadas entre si e com o estado da arte, em diversos experimentos, incluindo bases de dados artificiais e reais. Essas duas novas formas de agregação não só reduziram significa- tivamente a quantidade de biclusters, essencialmente defragmentando os biclusters originais, mas também aumentaram consistentemente a qualidade da solução, medida em termos de precisão e recuperação, quando os biclusters são conhecidos previamente / Abstract: Biclustering involves the simultaneous clustering of objects and their attributes, thus defin- ing local models for the two-way relationship of objects and attributes. Just like clustering, biclustering has a broad set of applications, ranging from an advanced support for recom- mender systems of practical relevance to a decisive role in data mining techniques devoted to gene expression data analysis. Initially, heuristics have been proposed to find biclusters, and their main drawbacks are the possibility of losing some existing biclusters and the inca- pability of maximizing the volume of the obtained biclusters. Recently efficient algorithms were conceived to enumerate all the biclusters, particularly in numerical datasets, so that they compose a complete set of maximal and non-redundant biclusters. However, the ability to enumerate biclusters revealed a challenging scenario: in noisy datasets, each true bicluster becomes highly fragmented and with a high degree of overlapping, thus preventing a direct analysis of the obtained results. Fragmentation will happen no matter the boundary condi- tion adopted to specify the internal coherence of the valid biclusters, though the degree of fragmentation will be associated with the noise level. Aiming at reverting the fragmentation, we propose here two approaches for properly aggregating a set of biclusters exhibiting a high degree of overlapping: one based on single linkage and the other directly exploring the rate of overlapping. A pruning step is then employed to filter intruder objects and/or attributes that were added as a side effect of aggregation. Both proposals were compared with each other and also with the actual state-of-the-art in several experiments, including real and artificial datasets. The two newly-conceived aggregation mechanisms not only significantly reduced the number of biclusters, essentially defragmenting true biclusters, but also consistently in- creased the quality of the whole solution, measured in terms of Precision and Recall when the composition of the dataset is known a priori / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Made available in DSpace on 2014-07-29T14:57:52Z (GMT). No. of bitstreams: 1 Dissertacao Diego Galindo Pecin.pdf: 448272 bytes, checksum: 755b351108c1082bc3bdb084b7add6ec (MD5) Previous issue date: 2010-02-23 / This dissertation addresses the optimization of the Elementary Shortest Path Problem with a Capacity Constraint (ESPPCC) and describes algorithms for its resolution that make use of concepts such as Label-Setting, Bidirectional Dynamic Programming and Decremental State Space Relaxation. These algorithms were used in a robust CVRP s Branch-and- Cut-and-Price framework as the column generation mechanism. The resulting BCP was used to obtain results (lower bounds, processing time and the number of branching nodes generated) to several CVRP s test instances. These results are compared with previous ones obtained with the original BCP, which is based on k-cycle elimination. Elementary routes are also explored in a route enumeration context, which allows the enumeration of all possible relevant elementary routes, i.e., all routes that have a chance of being part of an optimal CVRP s solution. If the number of relevant routes is not too large (say, in the range of tenths of thousands), the overall problem may be solved by feeding a general MIP solver with a set-partition formulation containing only those routes. If this set-partition can be solved, the optimal solution will be found and no branch will be necessary. Sometimes this leads to very significant speedups when compared to traditional branch strategies. / Esta dissertação aborda o Problema do Caminho Elementar Mínimo com Restrição de Capacidade (ESPPCC Elementary Shortest Path Problem with a Capacity Constraint) e descreve algoritmos para a sua resolução que fazem uso de conceitos tais como Correção de Rótulos, Programação Dinâmica Bidirecional e Relaxação Decrescente do Espaço de Estados. Esses algoritmos foram usados como geradores de rotas elementares no subproblema de geração de colunas de um algoritmo BCP robusto para o CVRP. Os resultados (limites inferiores, tempo de processamento e número de nós gerados) obtidos, para algumas instâncias de teste do CVRP, são comparados aos obtidos na versão original desse algoritmo BCP, que utiliza rotas não elementares sem 3-ciclos ou 4-ciclos. Rotas elementares também são exploradas em um contexto de enumeração para o CVRP, a qual permite obter rotas (usando um critério baseado em limites e em custo reduzido) que possuem uma chance de pertencer a uma solução ótima. Se o número de rotas não for muito grande (na ordem de poucos de milhares), então todo o problema pode ser resolvido como um problema de particionamento de conjuntos contendo apenas tais rotas. Algumas vezes isso acelera o algoritmo Branch-and-Bound consideravelmente, quando comparado com estratégias tradicionais de particionamento (branching), já que muitos nós da árvore podem ser resolvidos sem a geração de novos nós.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-11-10T14:15:57Z No. of bitstreams: 1 KLEBBER TEODOMIRO MARTINS FORMIGA - DISSERTAÇÃO PPGECA 1999..pdf: 16389709 bytes, checksum: 2cbf1a8342d988c0e6828ecd2fda1b6c (MD5) / Made available in DSpace on 2018-11-10T14:15:57Z (GMT). No. of bitstreams: 1 KLEBBER TEODOMIRO MARTINS FORMIGA - DISSERTAÇÃO PPGECA 1999..pdf: 16389709 bytes, checksum: 2cbf1a8342d988c0e6828ecd2fda1b6c (MD5) Previous issue date: 1999-03-11 / CNPq / As redes de distribuição, que fazem parte dos sistemas de abastecimento de água, são, em grande parte, redes malhadas, cuja complexidade no dimensionamento tem forçado os projetistas a utilizar metodologias tradicionais de tentativa e erro para obter a solução do problema. Esses métodos, dos quais o mais empregado é o de Hardy-Cross, fazem tão somente o balanceamento da rede, deixando a cargo da experiência do projetista a busca de um dimensionamento mais econômico. Neste trabalho será apresentado um método que utiliza técnicas de programação não linear para o dimensionamento económico de redes malhadas. Esse método é composto de duas etapas. Na primeira, as vazões e os diâmetros são considerados como variáveis de decisão, e na segunda etapa, as variáveis de decisão são os comprimentos dos segmentos dos trechos, com diâmetros constantes, e suas correspondentes vazões. Essa metodologia foi aplicada a duas redes encontradas na literatura, em que o dimensionamento já havia sido feito por outros métodos de otimização. Os resultados mostram que o método da programação não linear apresenta uma eficácia maior na busca do custo mínimo de uma rede, quando comparado com outras metodologias de otimização de redes malhadas estudadas. / The design complexity of looped networks has forced to use traditional trial and error methods to attain a solution for the problem. Those methods, where the Hardy-Cross method is the most known among them, only carry out energy and mass balance of the network without dealing with the system's cost, that is, nor estimating neither improving the system's cost. In this work, a method for designing economical looped networks based on nonlinear programming is presented. To reduce the number of variables and, probabily, improve the performance of the solution procedure, this method is composed of two stages to reach an optimal solution. In a first stage, a nonlinear programming technique is applied to determine the flows and diameters of the pipes connecting two nodes of the network. In a second stage are chosen which are the upper and lower values of the results attained at the first stage for each pipe segment, and a nonlinear programming technique is applied once more to determine the length of each diameter for each pipe segment along with its flow. In both stages the objective function was related to the cost of the pipes and pumping requirements. This method has been applied to two examples of looped networks, which have been used in the literature to illustrate the application of other optimization methods developed by other authors. The optimal solutions attained from the method presented herein have shown to be better than the ones resulting from the application of any other method, which were taken into account for comparison in this work.