Ordem topológica descreve fases da matéria que não são caracterizadas apenas pelo esquema de quebra de simetria de Landau. Em 2-dimensões ordem topológica é caracterizada, entre outras propriedades, pela existência de uma degenerescência do estado fundamental que é robusta sobre perturbações locais arbitrarias. Com o proposito de entender o que caracteriza e classifica ordem topológica 3-dimensional o presente trabalho apresenta um modelo quântico exatamente solúvel em 3-dimensões que generaliza os modelos em 2-dimensões baseados em teorias de gauge. No modelo proposto o grupo de gauge é substituído por um 2-grupo. A Hamiltonia, que é dada por uma soma de operadores locais, é livre de frustrações. Provamos que a degenerescência do estado fundamental nesse modelo é dado pelo invariante de Yetter da variedade 4-dimensional Sigma × S¹, onde Sigma é a variedade 3-dimensional onde o modelo está definido. / Topological order describes phases of matter that cannot be described only by the symmetry breaking theory of Landau. In 2-dimensions topological order is characterized, among other properties, by the presence of a ground state degeneracy that is robust to arbitrary local perturbations. With the purpose of understanding what characterizes and classify 3-dimensional topological order this works presents an exactly soluble quantum model in 3-dimensions that generalize 2-dimensional models constructed using gauge theories. In the model we propose the gauge group is replaced by a 2-group. The Hamiltonian, that is given by a sum of local commuting operators, is frustration free. We prove that the ground state degeneracy of this model is given by the Yetters invariant of the 4-dimensional manifold Sigma × S¹, where Sigma is the 3-dimensional manifold the model is defined.

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-12-09T12:17:44Z No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2017-02-02T18:18:37Z (GMT) No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) / Made available in DSpace on 2017-02-02T18:18:37Z (GMT). No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) Previous issue date: 2016-10-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research analyses how an approach in the classroom via Problem Solving, Exploration and Posing can potentialize the teaching and learning of Combinatorial Analysis. A literature review was performed aiming to understand the contributions of other researchers on the researched theme, so that it could be possible to realize what is possible to deepen and add for the scientific community, regarding the teaching and learning process of the Combinatorial Analysis. Besides this, an interview with mathematics teachers was performed, aiming to know their ideas on teaching and learning of Combinatory Analysis and, afterwards, scrutinize until where they could help to plan a sequence of activities. The research was conducted according to a qualitative approach, aiming to search meanings, interpreting and comprehend the information obtained. The modality of research can be characterized as teacher research; according to which the professor is the researcher of his or her own classroom (LANKSHEAR AND KNOBEL, 2008). The teaching and learning Methodology chosen to work in the classroom was the one of the problem solving, exploration and posing, developed with a sequence of activities in a group of the 2nd year of Secondary School of a public school in the city of Alagoinha-PB, Brazil. During the intervention, this researcher acted as a researcher teacher, working in the classroom as a regent teacher, giving a utonomy to the students on the construction of the essential ideas of the Combinatory Analysis, in such a way that the author acted as a mediator and instigator. Data were collected during the lessons through observation and records of the materials used by the students, as well as sound recording. Twenty-one meetings were performed, totaling 25 lessons, each lesson lasting, at most, 45 minutes. The classroom was organized in groups of three students and, in some cases, in pairs, in order to carry out a cooperative and collaborative work, where it was considered important, in this process, the mutual respect among them, respecting the ideas arisen on the search of the problem solution. The results of the research highlighted that through the Mathematics teaching and learning approach via Problem Solving, Exploration and Posing it was possible to monitor the growth of the students, who created their own ideas to solve the problems, and, consequently, found multiple strategies for solution of them; posteriorly, justify their solutions, participating effectively of the construction of their knowledge. Besides this, the students engaged in activities of mathematical exploration, which enabled the comprehension of the essential ideas of Combinatorial Analysis, as well as assuming the role of investigators in the classroom, generalizing, formulating new problems and, afterwards, solving them. From which it follows that such methodology allows learning with more comprehension, strengthening the student to solve problems of Combinatorial Analysis with focus not only on the search of the problem solution, but also on the process of the solution and being able to go far beyond, like the performance of a work of problem posing and exploration. / A presente pesquisa analisa como uma abordagem em sala de aula via Resolução, Exploração e Proposição de problemas pode contribuir/potencializar com o ensino-aprendizagem de Análise Combinatória. Foi realizada uma revisão de literatura com o intuito de compreender as contribuições de outros pesquisadores acerca do tema pesquisado, para que se pudesse perceber o que é possível aprofundar e acrescentar para a comunidade científica, no que diz respeito ao processo de ensino-aprendizagem da Análise Combinatória. Além disso, foi realizada uma entrevista com professores de Matemática, com o intuito de conhecer as suas ideias acerca do ensino-aprendizagem de Combinatória e, posteriormente, perscrutar até que ponto elas poderiam colaborar a planejar uma sequência de atividades. A pesquisa foi empreendida segundo uma abordagem qualitativa, visando buscar significados, interpretar e compreender as informações obtidas. A modalidade de pesquisa pode ser caracterizada como pedagógica, segundo a qual o professor é o pesquisador de sua própria sala de aula (LANKSHEAR E KNOBEL, 2008). A Metodologia de ensino-aprendizagem escolhida para trabalhar em sala de aula foi a de resolução, exploração e proposição de problemas, desenvolvida com uma sequência de atividades em uma turma do 2ª ano do Ensino Médio de uma escola pública na cidade de Alagoinha-PB. Durante a intervenção, o presente pesquisador agiu como professor-pesquisador, trabalhando em sala de aula como professor regente, dando autonomia aos alunos na construção das ideias essenciais de Combinatória, de modo que o autor agiu como mediador e incentivador. Os dados foram levantados durante as aulas através das observações e registros dos materiais utilizados pelos alunos, bem como de gravação sonora. Foram realizados 21 encontros, totalizando 25 aulas, cada aula com duração de, no máximo, 45 minutos. A sala foi organizada em grupos de três alunos e, em alguns casos, em duplas, com o intuito de se realizar um trabalho cooperativo e colaborativo, onde se considerou importante, nesse processo, o respeito mútuo entre eles, respeitando as ideias levantadas na busca da solução dos problemas. Os resultados da pesquisa evidenciaram que através da abordagem via Resolução, Exploração e Proposição de problemas foi possível acompanhar o crescimento dos alunos, que criaram suas próprias ideias para resolver os problemas, e, consequentemente, encontraram múltiplas estratégias de resolução deles; posteriormente, justificam suas soluções, participando efetivamente da construção do seu conhecimento. Além disso, os alunos engajaram-se em atividades de exploração matemática que lhes possibilitaram a apreensão de ideias essenciais de Análise Combinatória, como também assumiram o papel de investigadores em sala de aula, fazendo generalizações, formulando novos problemas e, em seguida, os resolvendo. De onde se conclui que tal metodologia permitiu um aprendizado com mais compreensão, potencializando o aluno para resolver problemas de Análise Combinatória com foco não apenas na busca da solução do problema, mas no processo da resolução e podendo ir muito além, como a realização de um trabalho de proposição e exploração de problemas.

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T20:48:39Z (GMT). No. of bitstreams: 1 Ferber_DanielFelix_M.pdf: 2571168 bytes, checksum: 373e2b3bb3f1ca3735beb4c4303dc5d9 (MD5) Previous issue date: 2007 / Resumo: O principal objetivo deste trabalho é a elaboração de heurísticas para auxiliar no projeto de cabeamento de redes telefônicas. O cabeamento será tratado desde os armários de distribuição até as caixas terminais. O auxílio de uma ferramenta computacional especializada no projeto de novas redes telefônicas abre caminhos para a minimização de custos e também reduz sensivelmente o tempo de planejamento. Inicialmente, estuda-se o problema para se obter uma especificação minuciosa, acompanhada de um modelo matemático. Com estas informações, desenvolve-se diferentes estratégias para algoritmos baseados na heurística GRASP, e compara-se os resultados experimentais obtidos / Abstract: The main goal of these studies is the design of heuristics to support the planning of wire cabling on a phone network. The cabling will be handled from the central distribution point to terminal boxes. The assistance of a computational tool specialized in the design of phone networks raises new opportunities for cost reduction and decreases considerably the time spent designing the network. The problem is first studied in order to achieve a detailed specification with a mathematical model. Based on this information, several different strategies are laid out based on a heuristic called GRASP and the experimental results are compared. / Mestrado / Otimização Combinatoria / Mestre em Computação

O presente trabalho desenvolve uma extensão do problema de corte de estoque unidimensional no caso em que a demanda pelos vários tipos de itens não é exatamente conhecida. Para considerar a aleatoriedade, foi proposto um modelo de programação estocástica de dois estágios com recurso. As varáveis de primeiro estágio são os números de barras cortadas por padrão de corte, e as variáveis de segundo estágio, os números de itens produzidos em escassez e em escassez. O objetivo do modelo é minimizar o custo total esperado. Para resolver a relaxação linear do modelo, foram propostos um método exato baseado no método Simplex com geração de colunas e uma estratégia heurística, que considera o valor esperado da demanda na resolução do problema de corte de estoque. As duas estratégias foram comparadas, assim como a possibilidade de resolver o problema de corte ignorando as incertezas. Finalmente, observou-se que é mais interessante determinar o valor ótimo do modelo recurso quando o problema sofre mais influência da aleatoriedade / This paper presents an integer linear optimization model of large scale for the one-dimensional cutting stock problem in the case which a demand is considered a random variable. To take this randomness into account, the problem was formulated as a two-stage stochastic linear program with recourse. The first stage decision variables are given by the number of bars that has to be cut according to each pattern, and the second stage decision variables by the number of holding items or backordering items production. The model objective is minimizes the total expected cost. We propose two methods to solve the model linear relaxation, one of them it is a Simplex-based method with column generation. The second method is a heuristic strategy that adopted the expected value of demand. We compare both strategies and the possibly of ignoring uncertainties on model. Finally, we observe that is much more interesting to determine the optimal recourse model solution when we have problems that are more afected by randomness

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema._________________________________________________________________________________________ ABSTRACT: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution.

Made available in DSpace on 2016-12-23T14:33:39Z (GMT). No. of bitstreams: 1 Dissertacao_CRAVO_G_L_2009.pdf: 1278828 bytes, checksum: ebab7f313edc64bb51241b5c7d587d33 (MD5) Previous issue date: 2009-06-25 / This master s thesis presents an implementation of the GRASP meta-heuristic for solving the Multi-mode Resource constrained Problem of Scheduling Project (MRCPSP). The MRCPSP belongs to the class NP-Hard and therefore has received attention of many researchers. In this thesis, a case study problem of Scheduling Industrial Maintenance is viewed as a MRCPSP. The GRASP was tested with a set of benchmark tests obtained from PSPLIB (Project Scheduling Library). The results showed that the GRASP is a good strategy for solving MRCPSP instances. / Esse trabalho apresenta uma implementação da meta-heurística GRASP para a resolução do Problema de Escalonamento de Projetos com Restrições de Recursos e Múltiplos Modos de Processamento (MRCPSP). O MRCPSP é um problema da classe NP Difícil e por isso vem recebendo atenção dos pesquisadores. Nessa dissertação, também é apresentado um estudo de caso cujo problema de Programação de Manutenção Industrial é visto como um problema de escalonamento de projeto. O GRASP foi testado com o conjunto de instâncias do MRCPSP disponíveis na PSPLIB (Project Scheduling Problem Library). Os resultados obtidos mostraram que o GRASP proposto se configura como uma boa estratégia de solução para o MRCPSP.

Made available in DSpace on 2016-12-23T14:33:44Z (GMT). No. of bitstreams: 1 Dissertacao de Danuza Prada de Faria Alckmin.pdf: 676333 bytes, checksum: 0f5968628437ef878dc7f703ce48b8bf (MD5) Previous issue date: 2009-08-31 / Agrupamento de dados é uma tarefa que divide um conjunto de dados em subconjuntos de forma que elementos associados a um mesmo grupo sejam mais similares entre si do que em relação a elementos de outros grupos. Ao organizar os dados em grupos é possível identificar similaridades e diferenças entre eles, extrair informações relevantes e inferir conclusões úteis a respeito das características dos dados. O problema de agrupamento de dados pode ser considerado como uma tarefa de otimização, uma vez que se pretende encontrar a melhor combinação de partições dentre todas as combinações possíveis. Uma abordagem que pode ser aplicada para resolver o problema de agrupamento é o uso de metaheurísticas, que são procedimentos capazes de escapar de ótimos locais, pois o uso de métodos exatos se torna computacionalmente inviável. Entretanto, a maioria das metaheurísticas aplicadas ao problema de agrupamento não são escalonáveis para bases reais e comerciais, são mais efetivas nos casos em que a instância do problema é menor. O custo computacional necessário para calcular as soluções se torna maior em instâncias maiores do problema. Por esse motivo, procedimentos híbridos que exploram a combinação de metaheurísticas representam uma abordagem promissora para a resolução do problema de agrupamento. Este trabalho apresenta uma proposta de Algoritmo Genético Híbrido de Agrupamento que associa ao processo de busca global uma heurística de busca local e cuja população inicial é gerada por técnicas de agrupamento. Tais melhorias têm como objetivo direcionar a busca para soluções mais próximas do ótimo global. É realizada uma avaliação experimental em bases de dados reais e sintéticas com o objetivo de verificar se a abordagem proposta apresenta uma melhoria em relação aos algoritmos avaliados. O resultado dessa análise mostra que o algoritmo proposto apresenta um desempenho melhor do que quatro entre os seis algoritmos avaliados. Para complementar a análise é realizada uma avaliação do tempo de execução, cujo objetivo é quantificar a diferença entre a abordagem proposta e os demais algoritmos avaliados. O resultado mostra que o tempo de execução da abordagem proposta é viável, porém é consideravelmente maior do que os tempos de execução dos algoritmos considerados de rápida convergência / Clustering is a task that divides a data set in subgroups aiming that elements associated to one exactly group are more similar between themselves than elements of other groups. Organizing data in groups make it possible to identify similarities and differences between them, to extract useful information and conclusions regarding the data features. Clustering may be considered an optimization problem because it is intended to find the best combination of partitions among all possible combinations. An approach that can be applied to solve the clustering problem is the use of metaheuristics, which are procedures capable of escaping from local optima, once the use of exact methods is computationally infeasible. However, the majority of the metaheurísticas applied to clustering problem is not scalable for real or commercial bases. They are more effective for smaller instances of the problem trated. The computational cost necessary to calculate the solutions becomes greater in larger instances of the problem. For this reason, hybrid procedures that explore the combination of metaheuristics represent a promising approach for solving the clustering problem. This work shows a proposal of a Hybrid Genetic Clustering Algorithm that associates the process of global search to a local search heuristic and also initializes the population by different grouping techniques. Such improvements aim to direct the search for solutions next to the global optimal one. An experimental evaluation with real and synthetic databases is performed aiming to verify if the proposed approach presents an improvement in relation to the other evaluated algorithms. The result of this analysis shows that the proposed algorithm presents a better performance in four among the six evaluated algorithms. In addition, an analysis of the execution time shows that the execution time of our proposal is feasible, even though it is considerably longer than the execution times of the fast convergence algorithms

Made available in DSpace on 2016-12-23T14:33:47Z (GMT). No. of bitstreams: 1 Kamila Ribeiro Ghidetti parte 1 p 1-60.pdf: 1277319 bytes, checksum: 04f11c251510276dd05a0c29559e9cb9 (MD5) Previous issue date: 2011-07-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A análise da influência dos algoritmos de reordenamento de matrizes na resolução de sistemas lineares utilizando os m´métodos iterativos não estacionários GMRES e Gradiente Conjugado, ambos com e sem precondicionamento, é o objeto de estudo desse trabalho. Os algoritmos mais referenciados na literatura para reordenamento de matrizes são Reverse Cuthill-McKee (RCM), Gibbs-Poole-Stockmeyer (GPS), Nested Dissection (ND) e Espectral (ES). Neste trabalho esses algoritmos foram analisados e algumas modificações foram propostas. Todos os algoritmos e suas versões modificadas foram implementados e comparados quanto a qualidade de solução (minimização de largura de banda e minimização de envelope) e tempo de execução. Além disso, os sistemas lineares associados as matrizes esparsas são resolvidos via m´métodos iterativos tipo Krylov precondicionados. Os precondicionadores analisados nesse estudo são baseados na fatoração LU incompleta. Para os testes computacionais é considerado um conjunto de matrizes estruturalmente simétricas oriundas das mais diversas áreas do conhecimento. Nossos estudos concluem que o reordenamento das matrizes, na maioria dos casos, reduz o numero de iterações dos métodos iterativos, entretanto a redução do tempo de processamento é dependente da dimensão e do condicionamento da matriz / This work analyzes the influence of matrices reordering algorithms on solving linear systems using non-stationary iterative methods GMRES and Conjugate Gradient, both with and without preconditioning. The algorithms referenced most often in the literature for the reordering of matrices are Reverse Cuthill-McKee (RCM), Gibbs-Poole-Stockmeyer (GPS), Nested Dissection (ND) and Spectral (ES). We analyze these algorithms and propose some modifications comparing their solution qualities (minimizing bandwidth and minimizing envelope) and CPU times. Moreover, the linear systems associated with sparse matrices are solved via preconditioned Krylov-type iterative methods considering the incomplete LU factorization preconditioners. For the computational tests, we consider a set of structurally symmetric matrices that can come from various fields of knowledge. We conclude that the reordering of matrices, in most cases, reduces the number of iterations in the iterative methods, but the reducing of the CPU time depends on the size and conditioning of the matrix

Orientador: Prof. Dr. Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2018. / Diversos problemas da area de otimização combinatoria podem ser convertidos, em tempo polinomial, para o problema de Programação Quadratica Binaria Irrestrita (UBQP). Neste problema, desejamos encontrar um vetor solução binario x, de dimensão n, tal que a função objetivo f(x) = x|Qx tenha valor mínimo, onde Q é uma matriz com coeficientes racionais. Em termos de complexidade computacional, o problema UBQP pertence a classe NP-difícil. A importancia deste problema, tanto pratica quanto teorica, tem motivado muitos pesquisadores a dedicarem uma quantidade razoavel de tempo tentando projetar tecnicas de resolução exatas e heuristicas para este problema. Durante o processo de resolução do problema UBQP, estas tecnicas necessitam reavaliar muitas vezes o valor da função objetivo. Dependendo da maneira como esta reavaliação é realizada, pode ser preciso executar um numero relativamente grande de operações elementares (atribuições, adições, subtrações e comparações). Isto pode consumir muito tempo de processamento quando n é grande. Nesta pesquisa, propomos formulas que requerem poucas operações para efetuar a reavaliação. Na literatura do problema UBQP, formulas de reavaliação são aplicadas, normalmente, quando há ate duas alterações nos componentes do vetor solução. As formulas que deduzimos podem ser usadas para efetuar qualquer quantidade de alterações. Analisamos uma das nossas formulas de maneira teorica e deduzimos funções que podem ser adotadas para indicar o melhor momento para aplicar essa formula. Ademais, projetamos algoritmos com estas formulas de reavaliação e verificamos a praticidade destes algoritmos conduzindo experimentos computacionais usando implementações de heurísticas de busca local e Variable Neighborhood Search. Nesses experimentos comparamos o desempenho dessas implementações ao resolver instancias da literatura para o problema UBQP. Os resultados experimentais evidenciaram que as formulas de reavaliação, propostas, podem propiciar reduções relativamente grandes nos tempos de processamento, mesmo quando o numero de diferenças entre soluções é moderadamente grande. / Several combinatorial optimization problems can be reformulated, in polynomial time, to the Unconstrained Binary Quadratic Programming (UBQP) problem. In this problem, we are interested in finding an n-dimensional binary solution vector, x, that minimizes the objective function f(x) = x|Qx, where Q is a matrix with rational coecients. In terms of computational complexity, the UBQP problem belongs to the NP-hard class. The practical and theoretical importance of this problem has motivated many researchers to dedicate a reasonable amount of time developing exact and heuristic solution techniques to solve this problem. During the resolution process of the UBQP problem, these techniques need to evaluate many times the objective function value. Depending on how it is made, it may be necessary to execute a relatively large number of elementary operations, such as assignments, additions, subtractions and comparisons. For n large, this may be time consuming. In this research, we propose formulas to perform the reevaluation requiring lesser operations than the simple evaluation of the objective function. In the literature of the UBQP problem, it is common to use reevaluation formulas only when there are at most two- ip moves that simultaneously change the values of two components. The formulas we have deduced can be used to evaluate any number of ip moves. We analyzed one of our reevaluation formulas and deduced functions that can be used to suggest the best moment to apply this formula. In addition, we designed algorithms with these reevaluation formulas and verified the practicality of these algorithms by conducting computational experiments using implementations of local search and Variable Neighborhood Search heuristics. In these experiments, we compared the performance of these implementations by solving benchmark instances for the UBQP problem. The experimental results showed that the reevaluation formulas we created can provide relatively large reductions in processing times, even when the number of ip moves is moderately large.