PPGCC - Programa de Pós-graduação em Ciência da Computação
URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596
Navegar
15 resultados
Resultados da Pesquisa
Item Heurísticas matemáticas aplicadas ao problema de carregamento de contêineres.(2020) Oliveira, Kelly Márcia de; Toffolo, Túlio Ângelo Machado; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Silva, Everton Fernandes daEste trabalho tem seu foco no Problema de Carregamento de Contêineres (CLP, do inglês Container Loading Problem). Neste problema, deseja-se alocar caixas de forma retangular em contêineres de modo que todas as caixas sejam alocadas e o volume total dos contêineres usados seja o menor possível. Devido ao crescente número de encomendas enviadas mundialmente, há uma demanda por parte das empresas e da sociedade por métodos para alocar caixas em contêineres de forma eficiente. Ao realizar o carregamento de caixas, as seguintes restrições devem ser satisfeitas: todas as caixas devem ser alocadas; caixas não podem se sobrepor dentro de um contêiner; e caixas devem ser alocadas inteiramente dentro da área do contêiner. Este trabalho propõe duas heurísticas matemáticas para o CLP, baseadas em Relax-and-fix e Local Branching. As duas estratégias utilizam métodos construtivos para produzir uma solução inicial e, em seguida, realizam uma busca local utilizando um modelo de programação inteira mista. Embora o Local Branching, assim como o Relax-and-fix, tenha sido capaz de encontrar uma solução até pouco tempo desconhecida para uma instância, resultados indicam que o Relax-and-fix é um método mais promissor, pois é capaz de gerar mais soluções de qualidade, igualando por muitas vezes o melhor resultado conhecido na literatura.Item Conflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.(2020) Brito, Samuel Souza; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Fonseca, George Henrique Godim da; Mateus, Geraldo Robson; Aragão, Marcus Vinicius Soledade Poggi de; Toffolo, Túlio Ângelo MachadoThis thesis addresses the development of con ict graph-based algorithms for MixedInteger Linear Programming, including: (i) an e cient infrastructure for the construction and manipulation of con ict graphs; (ii) a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; (iii) a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are 19.65% stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, 3.62 times better than those attained by the clique cut separator of the GLPK solver and 4.22 times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities; (v) two diving heuristics capable of generating integer feasible solutions in restricted execution times. Additionally, we generated a new version of the COIN-OR Branch-and-Cut (CBC) solver by including our con ict graph infrastructure, preprocessing routine and cut separators. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by 23.53%.Item Abordagem exata e heurísticas para o problema de planejamento de ordens de manutenção de longo prazo : um estudo de caso industrial de larga escala.(2018) Aquino, Roberto Dias; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Carvalho, Marco Antonio Moreira de; Souza, Sérgio Ricardo deEste trabalho propõe uma modelagem de programação linear inteira mista e algoritmos meta-heurísticos para um problema real de planejamento de manutenção de longo prazo para uma planta de beneficiamento de minério de ferro no Brasil. Este é um problema complexo de programação de ordens de manutenção preventiva, para o qual é necessário atribuir ordens de manutenção preventiva para as equipes de trabalho disponíveis em um horizonte de 52 semanas. Foi desenvolvido um modelo de programação inteira mista e os resultados foram utilizados como um benchmark. Como o modelo não foi capaz de resolver a instância real, foram propostos algoritmos meta-heurísticos para resolvê-la. Esses algoritmos foram baseados nos métodos Simulated Annealing, Variable Neighborhood Search, Multi-Start, Biased Random-Key Genetic Algorithm e algoritmos meméticos. Os algoritmos heurísticos desenvolvidos foram capazes de resolver a instância real, assim como melhorar a maioria dos resultados das instâncias de dimensões menores, levando a novos benchmarks.Item Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.(2018) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias ClaudioO Problema de Escalonamento de Tarefas em Máquinas Flexíveis Paralelas Idênticas com Restrições de Ferramentas, consiste em alocar tarefas a um conjunto de máquinas flexíveis paralelas, com o objetivo de minimizar o tempo máximo de processamento das tarefas pelas máquinas. Especificamente, as tarefas possuem tempo de processamento igual em qualquer máquina, porém, possuem tempo de preparo prévio que depende de todas as tarefas anteriores sequenciadas na mesma máquina, devido a configurações de ferramentas nas máquinas flexíveis. Neste trabalho, este problema NP-Difícil é abordado utilizando-se a metaheurística paralela Algoritmo Genético de Chaves Aleatórias Viciadas hibridizada com procedimentos de busca local organizados em uma Descida em Vizinhança Variável. São apresentados resultados inéditos para um conjunto de 2880 instâncias da literatura, incluindo resultados ótimos para 12,31% entre as menores instâncias. O método proposto é comparado ao atual estado da arte e obtém 91,81% das melhores soluções. Novas melhores soluções são apresentadas para 52,75% do total de instâncias. Adicionalmente, o método proposto apresenta tempo de execução 92,69% menor, dominando assim o atual estado da arte.Item Discretizador heurístico para o contexto de classificação hierárquica.(2016) Galvão, Leandro Ribeiro; Merschmann, Luiz Henrique de Campos; Silla Júnior, Carlos Nascimento; Pappa, Gisele Lobo; Ferreira, Almeida FerreiraDiferentes tipos de problemas de classificação podem ser encontrados na literatura, cada qual possuindo seu nível de complexidade. Diversos algoritmos de aprendizado de máquina requerem atributos discretos e nesses casos o pré-processamento da base de dados né necessário. Na literatura, os trabalhos apresentam diversos métodos de discretização, porém até o momento, não há nenhum método de discretização supervisionado projetado para ser utilizada em conjunto com classificadores hierárquicos globais. Neste trabalho é proposto um método supervisionado de discretização capaz de lidar com bases do contexto de classificação hierárquica. Esse método corresponde a uma heurística, denominada Agglomerative Discretization Heuristic for Hierarchical Classification - ADH2C, que foi projetada para ser utilizada em conjunto com classificadores hierárquicos globais. A avaliação da qualidade da discretização realizada pela heurística ADH2C foi feita a partir de experimentos comparativos com métodos de discretização não-supervisionados Equal-Width (EW) e Equal-Frequency (EF). A qualidade da discretização foi medida por meio do desempenho preditivo pelo classificador hierárquico Global Model Naive Bayes (GMNB) utilizando-se 9 bases de dados de bioinformática pré-processadas pelos métodos de discretização EW, EF e ADH2C. Os experimentos realizados neste trabalho mostraram que para a maioria das bases de dados utilizadas, o classificador GMNB alcançou o melhor desempenho preditivo (hF) quando utilizou as bases de dados pré-processadas pela heurística ADH2C. A melhora no desempenho preditivo do GMNB, utilizando as bases de dados pré-processadas pela heurística ADH2C, evidencia sua aplicabilidade no contexto de classificação hierárquica monorrótulo.Item Desenvolvimento de técnicas de seleção de atributos no contexto da classificação hierárquica monorrótulo.(2015) Dias, Thieres Nardy; Merschmann, Luiz Henrique de CamposA 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.Item Algoritmos exatos e heurísticos para a resolução do problema da descoberta de cliques de peso máximo.(2015) Vilas Boas, Matheus Guedes; Santos, Haroldo GambiniO presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos e heurísticos, sequenciais e paralelos, para a resolução do problema da enumeração de cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com vértices ponderados, onde o objetivo é 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 é 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ção foi realizada para resolver o PECPL. Além disso, várias melhorias foram propostas a fim de melhorar a eficiê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 modificados para refletir o problema abordado no presente trabalho. Porém, a metaheurística Simulated Annealing foi proposta e desenvolvida utilizando-se as mesmas estruturas de vizinhança utilizadas na heurística busca tabu com multivizinhanças. A diferença das duas técnicas está 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 à separação de cortes em problemas formulados por meio do uso de programação 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 à resolução do PECPL, os resultados obtidos comprovam a eficiê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écnicas. Quando a análise dos resultados foi direcionada à resolução do PCPM, todas as técnicas implementadas obtiveram bons resultados, com destaque para a heurística busca tabu com multi-vizinhanças, a qual resolveu todas as instâncias de forma ótima, com o menor tempo computacional em relação às demais abordagens. Como trabalhos futuros, são sugeridos a adoção de operadores lógicos para a representação do grafo no algoritmo de Bron-Kerbosch, a melhoria da versão paralela do algoritmo e o estudo do projeto das metaheurísticas Simulated Annealing e busca tabu.Item Grafo de conflitos : construção e aplicações em problemas de programação inteira.(2015) Brito, Samuel Souza; Santos, Haroldo GambiniEste trabalho explora a informação estrutural de relações entre variáveis binárias em problemas de Programação Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construção de métodos exatos e heurísticos de resolução. Nesse sentido, o presente trabalho propõe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtenção de soluções factíveis e limites duais fortes para problemas de Programação Inteira. Foram desenvolvidas otimizações nas técnicas de detecção de conflitos, que permitiram a construção rápida de grafos densos mediante a análise de restrições. A obtenção de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geração de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ímpar e inseri-los na relaxação linear, reforçando os limites duais e acelerando a convergência para a solução ótima. Para obter soluções factíveis para programas binários foi desenvolvido um resolvedor heurístico, que utiliza as relações lógicas entre variáveis para construir uma solução inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteração, que permite corrigir a infactibilidade de uma solução ou, até mesmo, saltar de uma solução factível para outra. Considerando a produção de limites duais fortes, os resultados obtidos pela rotina de geração de desigualdades desenvolvida mostraram uma convergência mais rápida em relação à rotina de separação de cortes do resolvedor COINOR Branch-and-Cut. Em relação à obtenção de factibilidade, o resolvedor heurístico foi apto a gerar soluções para um número significativo de problemas de Programação Inteira Binária, considerando tempos restritos de execução.Item Novos algoritmos para o problema de sequenciamento em Máquinas Paralelas não relacionadas com tempos de preparação dependentes da sequência.(2014) Cota, Luciano Perdigão; Souza, Marcone Jamilson FreitasEste 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.Item pRINS : uma matheurística para problemas binários.(2014) Gomes, Thiago Macedo; Souza, Marcone Jamilson FreitasUma 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.