Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Marise Leite (marise_mg@yahoo.com.br) on 2016-03-21T15:04:55Z No. of bitstreams: 2 license_rdf: 23748 bytes, checksum: b92763cfc0af52c7c868455edfaf3266 (MD5) DISSERTAÇÃO_DesenvolvimentoTécnicasSeleção.pdf: 1727478 bytes, checksum: ed2ee4abaae76a146068a3c08700af4e (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2016-03-22T13:57:02Z (GMT) No. of bitstreams: 2 license_rdf: 23748 bytes, checksum: b92763cfc0af52c7c868455edfaf3266 (MD5) DISSERTAÇÃO_DesenvolvimentoTécnicasSeleção.pdf: 1727478 bytes, checksum: ed2ee4abaae76a146068a3c08700af4e (MD5) / Made available in DSpace on 2016-03-22T13:57:02Z (GMT). No. of bitstreams: 2 license_rdf: 23748 bytes, checksum: b92763cfc0af52c7c868455edfaf3266 (MD5) DISSERTAÇÃO_DesenvolvimentoTécnicasSeleção.pdf: 1727478 bytes, checksum: ed2ee4abaae76a146068a3c08700af4e (MD5) Previous issue date: 2015 / A seleção de atributos, tradicionalmente adotada como uma etapa de pré-processamento dos dados, tem como objetivo principal identificar os atributos relevantes para a tarefa de classificação. No entanto, para o cenário de classificação hierárquica, onde as classes a serem preditas estão estruturadas de acordo com uma hierarquia, poucos trabalhos na literatura apresentam propostas de técnicas de seleção de atributos. Mais especificamente, para problemas de classificação hierárquica monorrótulo, não foram encontradas na literatura técnicas de seleção de atributos que possam ser utilizadas em conjunto com classificadores hierárquicos globais, ou seja, classificadores que são treinados levando-se em consideração toda a hierarquia de classes de uma só vez. Desse modo, neste trabalho propomos uma adaptação da medida Incerteza Simétrica (Symmetrical Uncertainty { SU) para permitir que ela possa ser utilizada em técnicas de seleção de atributos para problemas de classificação hierárquica monorrótulo que usam classificadores hierárquicos globais. Posteriormente, utilizamos essa adaptação proposta, denominada Incerteza Simétrica Hierárquica (Hierarchical Symmetrical Uncertainty { SUH), em duas técnicas distintas de seleção de atributos: uma que faz uso da abordagem Filtro e outra que segue uma abordagem Híbrida (Filtro e Wrapper). A técnica que implementa a abordagem Híbrida corresponde a uma heurística que utiliza o classificador hierárquico Global-Model Naive Bayes (GMNB) para avaliar os subconjuntos de atributos. A partir das duas técnicas de seleção de atributos propostas neste trabalho, pudemos verificar a adequação da adaptação da medida SU para o cenário hierárquico. Além disso, o método heurístico proposto, nomeado como Hybrid Feature Selection for Hierarchical Classification (HFS4HC), apresentou resultados bastante promissores para o contexto da classificação hierárquica monorrótulo. ____________________________________________________________________________________________________________________ / ABSTRACT: Feature selection, usually adopted as a preprocessing step, aims at identifying as much relevant features as possible with the goal of improving classification accuracy. However, for hierarchical classification scenario, where the classes to be predicted are arranged in a hierarchy, there are few studies in literature that address feature selection techniques. More specifically, for hierarchical single-label classification problems, to the best of our knowledge, there is no work in the literature that addresses feature selection in conjunction with global hierarchical classifiers. Thus, in this work we propose an adaptation of the measure Symmetrical Uncertainty (SU) to allow it to be used in feature selection techniques for hierarchical single label classification problems using global hierarchical classifiers. Thereafter, we used this adaptation proposal called Hierarchical Symmetrical Uncertainty (SUH) in two distinct techniques for feature selection: one makes use of the filter approach and another follows a hybrid approach (filter and wrapper). The technique that implements a hybrid approach corresponds to a heuristic that uses the hierarchical classifier Global-Model Naive Bayes (GMNB) for assessing the feature subsets. From the two feature selection techniques proposed in this work, we could verify the appropriateness of the measure SU tailored to hierarchical context. Besides, the proposed heuristic method, called Hybrid Feature Selection for Hierarchical Classification (HFS4HC), presented promising results for the context of hierarchical single label classification.

Orientadores: Luis Gimeno Latre, Maria Teresa Moreira Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T18:55:43Z (GMT). No. of bitstreams: 1 Pessoa_MarcosirisAmorimdeOliveira_M.pdf: 1025610 bytes, checksum: 1115cdec51d5e1f718aac28413cb39ad (MD5) Previous issue date: 2003 / Mestrado

Orientadores: Luis Gimeno Latre, Maria Teresa Moreira Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T19:01:21Z (GMT). No. of bitstreams: 1 EstombeloMontesco_RichardAndres_M.pdf: 1813584 bytes, checksum: 220cb8c19a9560dd5d82345e45ec70c5 (MD5) Previous issue date: 2003 / Mestrado

Orientadores: Vinicius Amaral Armentano, Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-17T11:43:08Z (GMT). No. of bitstreams: 1 Scrich_CintiaRigao_M.pdf: 3723231 bytes, checksum: 483aa81bf811c8aab10a3b008d8a02fa (MD5) Previous issue date: 1992 / Resumo: O problema de dimensionamento de lotes de múltiplos itens com restrição de capacidade consiste na determinação das quantidades a serem produzidas em diferentes períodos de tempo na presença de restrição no recurso disponível. O modelo apresentado neste trabalho considera que a produção de um item em um dado período incorre em um custo fixo e um tempo de preparação. Para a resolução deste problema um método heurístico é desenvolvido. Além disso, é feita uma adaptação das técnicas de Busca Tabu a este método. Experimentos computacionais são apresentados e analisados / Abstract: The multi-item single-level capacitated lot-sizing problem consists in the determination of the amounts being produced in different periods of time in the presence of restriction on the available resources. The model presented in this work considers that the item production implies a setup cost and a setup time. To solve this problem a heuristic method is developed. Besides, an adaptatton of Tabu Search techniques for this method is done. Computational experiments are presented and analysed. / Mestrado / Mestre em Engenharia Elétrica

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-09-29T16:05:40Z No. of bitstreams: 2 license_rdf: 21174 bytes, checksum: b98541e59f955f816d2d78f2222e44c8 (MD5) DISSERTAÇÃO_MetaheurísticasBuscaTabu.pdf: 1081988 bytes, checksum: 1df813c1c7108a23fd54b5fd3f7e804c (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-07T13:01:18Z (GMT) No. of bitstreams: 2 license_rdf: 21174 bytes, checksum: b98541e59f955f816d2d78f2222e44c8 (MD5) DISSERTAÇÃO_MetaheurísticasBuscaTabu.pdf: 1081988 bytes, checksum: 1df813c1c7108a23fd54b5fd3f7e804c (MD5) / Made available in DSpace on 2014-11-07T13:01:18Z (GMT). No. of bitstreams: 2 license_rdf: 21174 bytes, checksum: b98541e59f955f816d2d78f2222e44c8 (MD5) DISSERTAÇÃO_MetaheurísticasBuscaTabu.pdf: 1081988 bytes, checksum: 1df813c1c7108a23fd54b5fd3f7e804c (MD5) Previous issue date: 2013 / O Problema de Rodízio das Tripulações (PRT) do sistema de transporte público consiste em atribuir a cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas.Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas. Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas. __________________________________________________________________________ / ABSTRACT: The Crew Rostering Problem (CRP) of public transportation system consists in assigning, for each crew, a sequence of journeys over the days in the planning horizon. As the daily journeys have different durations, the sequences can result in an accumulation of overtime or idle hours. Thus, the goal of the CRP is to minimize the overtime in the schedule, compensating them with idleness between journeys. This is the principle of the bank of hours allowed by the legislation, subject to operational restrictions and labor laws. In this work, the problem was solved using Tabu Search algorithm. First is generated the initial solution by greedy search. The generated solution is feasible, though the costs are high. Then the journeys are used to created the rost and through viable changes it tries to decrease the cost of each rostering with different implemented versions of Tabu Search. Four versions have been implemented: the first version, BTMP, which has shorter local search stops when it finds a better neighbor; the second, so-called BTMV, wherein the local search is performed over the entire neighborhood; the third, BTPV, using a criterion percentage variable to search for the best neighbor and the fourth version BTID, which uses criteria intensification and diversification for Tabu Search. When mounting a rostering should be considered the respite of the crews throughout the period. Subsequently, the results were compared to those obtained in the work of Prates e Silva (2012) that uses VNS metaheuristic. The results show that the implementations of the model developed take advantage of the characteristics of each stage, generating more economic solutions.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-11-20T16:36:46Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-20T16:39:12Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Made available in DSpace on 2014-11-20T16:39:12Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) Previous issue date: 2014 / Uma importante técnica para resolver problemas de otimização é por meio de Programação Inteira Mista (MIP, do inglês Mixed Integer Programming). Uma formulação MIP de um problema envolve um conjunto de variáveis, um conjunto de restrições sobre estas variáveis, um conjunto de restrições de integralidade e uma função objetivo linear a otimizar. Aplicações em otimização inteira são encontradas em diversas àreas do conhecimento, incluindo-se roteamento de veículos, alocação de enfermeiros, programação de horários, entre outros. O uso de métodos heurísticos tem sido empregado na resolução de problemas MIP como uma forma de acelerar o processo de busca na árvore de branching. Este trabalho propõe uma adaptação da heurística MIP Relaxation Induced Neighborhood Search (RINS), que explora a ideia de fixar variáveis de mesmo valor na solução inteira e fracionária corrente. O método proposto, denominado pRINS, explora explicitamente técnicas de pré-processamento, procurando sistematicamente por um número ideal de fixações, visando a produzir sub-problemas de tamanho controlado. As variáveis a fixar são organizadas por meio de um vetor de prioridade, sendo propostas três maneiras de escolha destas variáveis, cada uma delas dando origem a uma variante do método. Em seguida, os problemas são criados e resolvidos de modo semelhante ao método Variable Neighborhood Descent até que um critério de parada seja satisfeito. Os resultados das variantes do método foram comparados com os do resolvedor COIN-OR e CBC stand-alone e com o método RINS original. Pelos resultados obtidos, o método proposto se mostrou com desempenho superior a essas duas técnicas. ______________________________________________________________________________________________ / ABSTRACT: An important technique for solving optimization problems is Mixed Integer Programming (MIP). A MIP formulation for a problem involves a set of variables, a set of constraints on these variables, a set of integrality constraints and a linear objective function to optimize. Applications in integer programming are found in many areas of knowledge, including vehicle routing, traveling salesman problem, nurse scheduling and school timetabling. Heuristic methods have been employed in solving MIP problems as a way to accelerate the search process in the branching tree. This dissertation proposes an adaptation of the MIP heuristic Relaxation Induced Neighborhood Search (RINS), which explores the idea of fixing variables with same value in integer and fractional current solutions. The proposed method, named pRINS, explicitly explores pre-processing techniques, systematically searching for the ideal number of fixations to produce sub-problems of controlled size. Candidate variables to be fixed are ranked and three different strategies to select among them were evaluated. Then, problems are created and solved similarly to the Variable Neighborhood Descent method until a stopping criterion is met. The results of the variants were compared to the COIN-OR CBC stand-alone solver and the original RINS method. The results indicate that pRINS presents a better heuristic behavior than other techniques.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Maurílio Figueiredo (maurilioafigueiredo@yahoo.com.br) on 2015-01-13T18:37:57Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-01-15T17:28:11Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Made available in DSpace on 2015-01-15T17:28:11Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) Previous issue date: 2014 / Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas Não- Relacionadas com Tempos de Preparação Dependentes da Sequência (UPMSPST, do inglês Unrelated Parallel Machine Scheduling Problem with Setup Times), objetivando minimizar o makespan. Para resolvê-lo foram desenvolvidos três algoritmos heurísticos e um algoritmo híbrido. O primeiro algoritmo heurístico, denominado HIVP, tem uma solução inicial gerada por um procedimento construtivo parcialmente guloso baseado no método Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time { ASPT. Essa solução e, posteriormente, refinada pelo procedimento Iterated Local Search { ILS, tendo o Random Variable Neighborhood Descent como método de busca local. Além disso, periodicamente a busca é intensificada e diversificada por meio de um procedimento Path Relinking { PR. No segundo algoritmo heurístico, denominado GIAP, a solução inicial é criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solução é refinada por um procedimento ILS que utiliza como método de busca local o procedimento Adaptive Local Search { ALS. A busca _e também intensificada e diversificada por meio de um procedimento PR. O terceiro e último algoritmo heurístico, denominado AIRP, tem sua solução inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solução é refinada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma análoga aos algoritmos anteriores, a busca também passa por uma intensificação ao e diversificação periodicamente por meio de um procedimento PR. O algoritmo híbrido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heurístico AIRP, diferindo deste por acrescentar um módulo de programação linear inteira mista. Para a aplicação desse módulo são selecionados um par de máquinas e subconjuntos de tarefas nessas máquinas. Esses subconjuntos são combinados e passam por uma busca local que consiste em acionar um resolvedor de programação matemática aplicado a melhor das formulações de programação matemática dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi possível concluir que o AIRP obteve os melhores resultados dentre os algoritmos heurísticos propostos, conseguindo superar vários outros algoritmos da literatura. Também foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRMP necessita de um tempo maior para acionar o módulo de programação matemática, esses experimentos utilizaram um tempo maior de execução. Observou-se, no entanto, que a adição do módulo de programação matemática não melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes também mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo e capaz de encontrar melhores soluções. __________________________________________________________________________________________________________________________ / ABSTRACT: This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times { UPMSPST, having as goal to minimize the makespan. In order to solve it, three heuristic algorithms and a hybrid algorithm were developed. The first heuristic algorithm, called HIVP, has an initial solution generated by a greedy constructive procedure based on the Heuristic-Biased Stochastic Sampling and on the Adaptive Shortest Processing Time { ASPT rule. This solution is then refined by the Iterated Local Search { ILS procedure, having the Random Variable Neighborhood Descent as local search method. Moreover, the search is periodically intensified and diversified by a Path Relinking { PR procedure. In the second algorithm, called GIAP, the initial solution is created by a procedure inspired on the Greedy Randomized Adaptive Search Procedures. This solution is then refined by an ILS procedure that uses the procedure Adaptive Local Search { ALS as local search method. The search is also intensified and diversified by a PR procedure. The third and final heuristic algorithm, called AIRP, has its initial solution generated by a greedy constructive procedure based on ASPT rule. This solution is then refined by the ILS, having as local search a procedure called RVI. Analogously to the previous algorithms, the search also applies periodically an intensification and diversification strategy based on the PR procedure. The hybrid algorithm, named AIRMP, is similar to the AIRP heuristic algorithm, differing from it by adding a module of mixed integer linear programming. To apply this module one pair of machines are selected and subsets of jobs of these machines. These subsets are combined and they pass through a local search that consists in running a mathematical programming solver applied to the best formulation among the studied and developed ones. By computational experiments it was concluded that the AIRP algorithm obtained the best results among the proposed heuristic algorithms, outperforming several other algorithms from the literature. Experiments were also conducted to compare the AIRMP and AIRP algorithms. As the AIRMP needs more time to execute the mathematical programming module, these experiments utilized a higher runtime. It was observed, however, that the addition of the mathematical programming module does not improved the performance of the AIRMP algorithm in the tested time and in the used structure of subsets of jobs. These tests also showed that increasing the processing time of the AIRP, the algorithm is able to find better solutions.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Universidade Federal de Ouro Preto. / Submitted by giuliana silveira (giulianagphoto@gmail.com) on 2016-02-16T17:53:54Z No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2016-02-19T13:16:22Z (GMT) No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Made available in DSpace on 2016-02-19T13:16:22Z (GMT). No. of bitstreams: 1 DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) Previous issue date: 2015 / O presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos e heur ísticos, sequenciais e paralelos, para a resolu c~ao do problema da enumera c~ao de cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com vertices ponderados, onde o objetivo e encontrar todos os cliques maximais com peso acima de um limiar. Os algoritmos estudados neste trabalho são aplicados na separa ção de cortes no contexto de Programa ção Inteira. Encontrar todos os cliques acima de um dado peso e equivalente ao problema de encontrar todas as desigualdades violadas de clique. Foram desenvolvidas adapta ções em algoritmos conhecidos na literatura, para a resolução do problema. Para o algoritmo de Bron-Kerbosch, uma adapta c~ao foi realizada para resolver o PECPL. Al em disso, v arias melhorias foram propostas a m de melhorar a efi ciência na resolu ção das instâncias do problema. Foram propostas uma versão iterativa do algoritmo, originalmente recursivo, e uma versão paralela. O algoritmo de Ostergard e a heur stica busca tabu com multi-vizinhanças tamb ém foram implementados e modi ficados para re etir o problema abordado no presente trabalho. Por m, a metaheur stica Simulated Annealing foi proposta e desenvolvida utilizando-se das mesmas estruturas de vizinhan ca utilizadas na heur stica busca tabu com multivizinhanças. A diferen ça das duas t ecnicas est a na estrat égia de resolu ção do problema: enquanto a primeira utiliza-se do conceito de lista tabu, a ultima simula o processo de recozimento de metais. Nos experimentos computacionais, foram utilizadas 7292 instâncias, oriundas de quatro conjuntos referentes a separa ção de cortes em problemas formulados por meio do uso de programa c~ao inteira. Os experimentos foram conduzidos em duas partes: em um primeiro momento, as instâncias foram utilizadas para resolu ção do PECPL. Posteriormente, o foco foi a resolu ção do problema do clique de peso m áximo (PCPM). Quanto a resolu c~ao do PECPL, os resultados obtidos comprovam a efi ciência do algoritmo de Bron-Kerbosch, quando comparado aos demais algoritmos, ao encontrar a solu ção ótima para todas as instâncias e em um tempo consideravelmente menor do que as outras t ecnicas. Quando a an alise dos resultados foi direcionada a resolu c~ao do PCPM, todas as t écnicas implementadas obtiveram bons resultados, com destaque para a heur stica busca tabu com multi-vizinhan cas, a qual resolveu todas as instâncias de forma ótima, com o menor tempo computacional em rela c~ao as demais abordagens. Como trabalhos futuros, são sugeridos a ado c~ao de operadores l ogicos para a representa c~ao do grafo no algoritmo de Bron-Kerbosch, a melhoria da vers~ao paralela do algoritmo e o estudo do projeto das metaheurí sticas Simulated Annealing e busca tabu. __________________________________________________________________________________ / ABSTRACT : This work deals with the design, implementation and evaluation of exact and heuristic algorithms, sequential and parallel to the resolution of clique enumeration problem with weight above a threshold (PECPL). This problem considers a graph with weighted vertices, where the goal is to nd all maximal cliques with weight above a threshold. The algorithms studied in this work are applied in the separation cuts in the context of Integer Programming. Find all clique above a certain weight is equivalent to the problem of nding all the inequalities violated clique. Adaptations were developed algorithms known in the literature, to solve the problem. For the Bron-Kerbosch algorithm, an adaptation was made to solve the PECPL. In addition, several improvements were proposed in order to improve e ciency in the resolution of problem instances. It has been proposed an iterative version of the algorithm, recursive originally, and a parallel version. The Ostergard algorithm and multi-neighborhoods tabu search heuristic were also implemented and modi ed to re ect the problem addressed in this paper. Finally, the Simulated Annealing metaheuristic was proposed and developed using the same neighborhood structures used in multi-neighborhoods tabu search heuristic. The di erence of the two techniques is in solving strategy problem: while the rst is used the concept of tabu list, the last simulates the process of annealing of metals. In the computational experiments, we used 7292 instances, belonging to four sets related to the separation cuts in problems formulated by using integer programming. The experiments were conducted in two parts: at rst, the instances were used for solving the PECPL. Later, the focus was on resolving the maximum weight clique problem (PCPM). As for the resolution of the PECPL, the results prove the e ciency of Bron-Kerbosch algorithm, when compared to other algorithms to nd the optimal solution for all instances and in a considerably shorter time than the other techniques. When analyzing the results was directed to resolving the PCPM, all techniques implemented performed well, particularly the multi-neighborhoods tabu search heuristic, which solved all instances optimally with less computational time compared to other approaches. As future work, it is suggested the adoption of logical operators for the representation of the graph in Bron-Kerbosch algorithm, improved parallel version of the algorithm and the study design of simulated annealing and tabu search metaheuristics.

Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T10:33:41Z (GMT). No. of bitstreams: 1 Longo_HumbertoJose_M.pdf: 2296998 bytes, checksum: cb6cef9a3b19187ee26dc91e8fe15b17 (MD5) Previous issue date: 1995 / Resumo: Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico, baseado no paradigma de Times Assíncronos. Um segundo objetivo desta dissertação, e de grande importância na funda­mentação do método ora proposto, é um estudo das principais características estruturais do problema; de sua formulação como um problema de programação linear inteira 0-1 e dos principais métodos computacionais (heurísticos e exatos) atualmente disponíveis para sua resolução. Times Assíncronos são organizações de software que visam a interação efici­ente entre vários algoritmos, para a resolução de problemas adequados à aborda­gem multi-algorítmica. A arquitetura proposta utiliza métodos aproximados para a resolução do SCP e do dual da relaxação linear do mesmo. Esta abordagem primal-dual permite garantir que a melhor solução encontrada esteja a um certo percentual da solução ótima, ou mesmo, eventualmente, provar a otimalidade da solução. Segundo este enfoque, os principais componentes da arquitetura proposta são algoritmos gulosos e de consenso, procedimentos de busca tabu, métodos de otimização por subgradientes e geradores de planos de corte. Os principais métodos exatos para a resolução do SCP são baseados em metodologias enumerativas. A maioria desses métodos combina ao esquema de enumeração diversas das técnicas heurísticas utilizadas na arquitetura aqui proposta. Contudo, esses métodos apresentam desempenho insatisfatório para algu­mas classes de instâncias, por não obterem boas soluções em um limite razoável de tempo. A arquitetura proposta foi aplicada a instâncias dessas classes de difícil reso­lução. Os resultados obtidos mostraram que é possível alcançar, com um esforço computacional aceitável, resultados no mínimo comparáveis aos dos melhores algoritmos para o SCP / Abstract: The development of an Asynchronous Team Method for heuristic resolution of the Set Covering Problem (SCP) is the main focus of this dissertation. Asynch­ronous Teams are software organizations that aim to efficient interaction among several algorithms for the resolution of problems that fit in a multi-algorithm approach. Another goal of this work is an extensive study of the SCP which covers: the SCP structures its formulation as a 0-1 ILP; and the description of the main heuristic and exact methods currently available for its resolution. This study is most1y required since we are concerned with the development of a multi-algorithm method. The resulting software architecture makes use of approximate algorithms for the resolution of the se P and its continuous relaxation dual. This primal-dual approach guarantees the best found solution to be at a certain percentage of the optimal solution and, eventually, proves the solution optimality. The main components of the proposed architecture are greedy and consensus algorithms, tabu search procedures, subgradient methods and cutting plane generators. The main exact methods for the se P resolution are based on enumerative methodologies. Most of these methods deploys many of the heuristic technics used in the proposed architecture to the enumeration scheme. However, these methods have a poor performance in some instance classes, because they do not obtain good solutions in a reasonable time limit. The proposed architecture was applied to particularly hard instances. The obtained results show that it is possible to reach solutions, at an acceptable computational effort, that are at least comparable to the ones obtained by the best algorithms for the SCP / Mestrado / Mestre em Ciência da Computação

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T03:48:35Z (GMT). No. of bitstreams: 1 Berretta_ReginaEsther_D.pdf: 9864278 bytes, checksum: ba475c4277cadec8953864df9f0375a7 (MD5) Previous issue date: 1997 / Resumo: Esse trabalho trata do problema dimensionamento de lotes em sistemas de produção multiestágio, que consiste na determinação das quantidades a serem produzidas em diferentes períodos, de tal modo que a demanda seja atendida. Por ser um sistema multiestágio de produção, os produtos dependem da compra e/ou produção de certos componentes. O modelo apresentado utiliza o conceito de estoque de escalão e considera custos de produção, estoque e preparação. Para retratar o consumo dos recursos, são incluídos tempos de preparação e produção. Além disso, supõe-se que o lead time de cada item seja diferente de zero. Para a resolução deste problema, foram desenvolvidos métodos heurísticos com o propósito de obter planos factíveis e buscar soluções com menor custo. Com o objetivo de melhorar o desempenho das heurísticas propostas, as técnicas meta- heurísticas Busca Tabu e Simulated Annealing foram incorporadas. Os resultados dos testes computacionais são comparados com a solução ótima em instâncias com até 60 variáveis binárias e para instâncias de maior porte, os resultados são comparados com um limitante inferior obtido pela aplicação de Relaxação Lagrangeana ao problema / Abstract: This thesis deals with the lotsizing problem in multistage production systems. The problem basically consists in determining the quantities to be produced in different periods of time such that a forecast demand would be attained. Since the production system is of a multistage type, the available items would be either produced or bought to satisfy the needs of the plan. The model we present uses the concept of echelon stock and considers production, stock and preparation costs. To model the aspects of consumption of resources, preparation and production times are also included in the mode!. In addition, the lead time of each item is supposed to be different from zero. In order to give feasible solutions for this problem we have developed heuristic methods which also lead to low cost solutions. In order to improve the performance of the developed heuristics, search techniques based on metaheuristics like "Tabu Search" and "Simulated Annealing" were introduced in a second stage. The results from the computational tests were compared with the optimal solution when the instances had up to 60 binary variables. For instances of a larger size the results were compared with a lower bound which was obtained by Lagrangean Relaxation of the problem's mixed-integer programming formulation / Doutorado / Doutor em Engenharia Elétrica