Navegando por Autor "Santos, Haroldo Gambini"
Agora exibindo 1 - 20 de 43
Resultados por página
Opções de Ordenação
Item 5th International Conference on Variable Neighborhood Search (ICVNS'17).(2018) Coelho, Vitor Nazário; Santos, Haroldo Gambini; Coelho, Igor Machado; Penna, Puca Huachi Vaz; Oliveira, Thays Aparecida de; Souza, Marcone Jamilson Freitas; Sifaleras, AngeloThis volume presents selected, peer-reviewed, short papers that were accepted for presentation in the 5th International Conference on Variable Neighborhood Search (ICVNS'17) which was held in Ouro Preto, Brazil, during October 2–4, 2017.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 An integer programming approach to the multimode resource-constrained multiproject scheduling problem.(2015) Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Araujo, Janniele Aparecida SoaresThe project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.Item An integer programming approach to the multimode resource-constrained multiproject scheduling problem.(2016) Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Soares, Janniele AparecidaThe project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.Item Analysis of stochastic local search methods for the unrelatedparallel machine scheduling problem.(2016) Santos, Haroldo Gambini; Toffolo, Túlio Ângelo Machado; Silva, Cristiano Luís Turbino de França e; Berghe, Greet VandenThis work addresses the unrelated parallel machine scheduling problem with sequence-dependent setup times,in which a set of jobs must be scheduled for execution by one of the several available machines. Each jobhas a machine-dependent processing time. Furthermore, given multiple jobs, there are additional setup times,which vary based on the sequence and machine employed. The objective is to minimiz e the schedule’s com-pletion time (makespan). The problem is NP-hard and of significant practical relevance. The present paperinvestigates the performance of four different stochastic local search (SLS) methods designed for solvingthe particular scheduling problem: simulated annealing, iterated local search, late acceptance hill-climbing,and step counting hill-climbing. The analysis focuses on design questions, tuning effort, and optimizationperformance. Simple neighborhood structures are considered. All proposed SLS methods performed signifi-cantly better than two state-of-the-art hybrid heuristics, especially for larger instances. Updated best-knownsolutions were generated for 901 of the 1000 large benchmark instances considered, demonstrating that par-ticular SLS methods are simple yet powerful alternatives to current approaches for addressing the problem.Implementations of the contributed algorithms have been made available to the research community.Item Automatic integer programming reformulation using variable neighborhood search.(2017) Brito, Samuel Souza; Santos, Haroldo GambiniChvatal-Gomory cuts are well-known cutting planes for Integer Programming problems. As shown in previous works, the inclusion of these cuts allows to significantly reducing the integrality gap. This work presents a Local Search heuristic approach based on Variable Neighborhood Search to discover violated Chv`atal-Gomory inequalities. Since this problem is known to be NP-hard, this approach was designed to generate violated inequalities in restricted amounts of time. Constraints are grouped in several sets, considering the amount of common variables. These sets are processed in parallel in order to obtain the best multipliers and produce violated cuts. We report some preliminary results obtained for MIPLIB 3.0 and 2003 instance sets, comparing our approach with an integer programming based separation method. Our algorithm was able to separate many violated inequalities, reducing the duality gap. Furthermore, it uses an extended numerical precision implementation, since it is not specifically bound to simplex based solvers.Item Caracterização e análise de uma rede de ingredientes e receitas.(2014) Ferreira, Willyan Michel; Souza, Fabrício Benevenuto de; Merschmann, Luiz Henrique de Campos; Silva, Ana Paula Couto da; Santos, Haroldo GambiniA troca de receitas é um hábito de muitas pessoas. Um meio online e colaborativo de compartilhar esse tipo de informação é através de websites especializados que permitem que usuários postem receitas, comentem e avaliem receitas existentes. Apesar de extremamente populares, pouco se sabe sobre esses sistemas e os padrões de interações que eles permitem. Visando preencher essa lacuna, esse trabalho apresenta uma extensa caracterização do site Tudo Gostoso, um importante site brasileiro de compartilhamento de receitas. Para isso, nós coletamos todas as receitas existentes no site juntamente com informações associadas aos comentários e avaliações. Além de explorar as interações existentes entre os usuários do site, nosso trabalho analisa uma rede formada por ingredientes que co-ocorrem em receitas e investiga a viabilidade de se extrair possíveis alterações nas receitas a partir de comentários dos usuários do site. Nossas análises revelam padrões de uso de ingredientes fundamentais da culinária brasileira e podem ser úteis para inspirar a construção de diversas novas aplicações, como ferramentas de recomendação de receitas.Item Combining an evolutionary algorithm with data mining to solve a single-vehicle routing problem.(2006) Santos, Haroldo Gambini; Ochi, Luiz Satoru; Marinho, Euler Horta; Drummond, Lúcia Maria de AssumpçãoThe aim of this work is to present some alternatives to improve the performance of an evolutionary algorithm applied to the problem known as the oil collecting vehicle routing problem. Some proposals based on the insertion of local search and data mining (DM) modules in a genetic algorithm (GA) are presented. Four algorithms were developed: a GA, a GA with a local search procedure, a GA including a DM module and a GA including local search and DM. Experimental results demonstrate that the incorporation of DM and local search modules in GA can improve the solution quality produced by this method.Item A communitarian microgrid storage planning system inside the scope of a smart city.(2016) Coelho, Vitor Nazário; Coelho, Igor Machado; Coelho, Bruno Nazário; Oliveira, Glauber Cardoso de; Barbosa, Alexandre Costa; Pereira, Leo; Freitas, Alan Robert Resende de; Santos, Haroldo Gambini; Ochi, Luiz Satoru; Guimarães, Frederico GadelhaIn this paper (a substantial extension of the short version presented at REM2016 on April 19–21, Maldives [1]), multi-objective power dispatching is discussed in the scope of microgrids located in smart cities. The proposed system considers the use of Plug-in Electric Vehicle (PEV) and Unmanned Aerial Vehicle (UAV) as storage units. The problem involves distinct types of vehicles and a community, composed of small houses, residential areas and different Renewable Energy Resources. In order to highlight possibilities for power dispatching, the optimization of three distinct goals is considered in the analysis: mini/ microgrid total costs; usage of vehicles batteries; and maximum grid peak load. Sets of non-dominated solutions are obtained using a mathematical programming based heuristic (Matheuristic). By analyzing cases of study composed with up to 70 vehicles, we emphasize that PEVs and UAVs can effectively contribute for renewable energy integration into mini/microgrid systems. Smart cities policy makers and citizens are suggested to consider the proposed tool for supporting decision making for cities under development, guiding their choices for future investments on renewable energy resources.Item A computational study of conflict graphs and aggressive cut separation in integer programming.(2015) Brito, Samuel Souza; Santos, Haroldo GambiniThis work explores the fast creation of densely populated conflict graphs at the root node of the search tree for integer programs. We show that not only the Generalized Upper Bound (GUB) constraints are useful for the fast detection of cliques: these can also be quickly detected in less structured constraints in O(n log n). Routines for the aggressive separation and lifting of cliques and odd-holes are proposed. Improved bounds and a faster convergence to strong bounds were observed when comparing to the default separation routines found in the current version of the COmputation INfrastructure for Operations Research (COIN-OR) Branch and Cut solver.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 Decision trees for the algorithm selection problem : integer programming based approaches.(2019) Vilas Boas, Matheus Guedes; Santos, Haroldo Gambini; Blum, Christian Clemens; Merschmann, Luiz Henrique de Campos; Silva, Rodrigo César Pedrosa; Toffolo, Túlio Ângelo MachadoEven though it is well known that for most relevant computational problems different algorithms may perform better on different classes of problem instances, most researchers still focus on determining a single best algorithmic configuration based on aggregate results such as the average. In this thesis, we propose Integer Programming based approaches to build decision trees for the Algorithm Selection Problem. These techniques allow the automation of three crucial decisions: (i) discerning the most important problem features to determine problem classes; (ii) grouping the problems into classes and (iii) select the best algorithm configuration for each class. We tested our approach from different perspectives: (i) univariate approach, where for each branch node, only one cutoff point of a feature is chosen and (ii) multivariate approach, where for each branch node, weights for multiple features are used (oblique decision trees). Considering the current scenario where the number of cores per machine has increased considerably, we also propose a new approach based on recommendation of concurrent algorithms. To evaluate our approaches, extensive computational experiments were executed using a dataset that considers the linear programming algorithms implemented in the COIN-OR Branch & Cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. We also conducted experiments with the scenarios/- datasets of the Open Algorithm Selection Challenge (OASC) held in 2017. Considering the first dataset and a 10-fold cross validation experiment, while selecting the single best solver across all instances decreased the total running time by 2%, our univariate approach decreased the total running time by 68% and using the multivariate approach, the total running time is decreased by 72%. An even greater performance gain can be obtained using concurrent algorithms, something not yet explored in the literature. For our experiments, using three algorithm configurations per leaf node, the total running time is decreased by 85%. These results indicate that our method generalizes quite well and does not overfit. Considering the results obtained using the scenarios of the OASC, the experimental results showed that our decision trees can produce better results than less interpretable models, such as random forest, which has been extensively used for algorithm recommendation.Item Drawing graphs with mathematical programming and variable neighborhood search.(2017) Silva, Cézar Augusto N.; Santos, Haroldo GambiniIn the Graph Drawing problem a set of symbols must be placed in a plane and their connections routed. To produce clear, easy to read diagrams, this problem is usually solved trying to minimize edges crossing and the area occupied, resulting in a NP-Hard problem. Our research focuses in drawing Entity Relationship (ER) diagrams, a challenging version of the problem where nodes have different sizes. Mathematical Programming models for the two solution phases, node placement and connection routing, are discussed and their exact resolution by an Integer Programming (IP) solver is evaluated. As the first phase proved to be specially hard to be solved exactly, a hybrid Variable Neighborhood Search (VNS) heuristic is proposed. Using IP techniques we obtained provably optimal (or close to optimal) solutions for the two different phases, at the expense of a large computational effort. We also show that our VNS based heuristic approach can produce close to optimal solutions in very short times for the hardest part of the solution process. Using either methods we have produced clearly better drawings than existing solutions.Item A general-purpose distributed computing Java middleware.(2019) Almeida, André Luís Barroso de; Cimino, Leonardo de Souza; Resende, José Estevão Eugênio de; Silva, Lucas Henrique Moreira; Rocha, Samuel Queiroz Souza; Gregorio, Guilherme Aparecido; Paiva, Gustavo Silva; Silva, Saul Emanuel Delabrida; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Aquino, André Luiz Lins de; Lima, Joubert de CastroThe middleware solutions for General‐Purpose Distributed Computing (GPDC) have distinct requirements, such as task scheduling, processing/storage fault tolerance, code portability for parallel or distributed environments, simple deployment (including over grid or multi‐cluster environments), collaborative development, low code refactoring, native support for distributed data structures, asynchronous task execution, and support for distributed global variables. These solutions do not integrate these requirements into a single deployment with a unique API exposing most of these requirements to users. The consequence is the utilization of several solutions with their particularities, thus requiring different user skills. Besides that, the users have to solve the integration and all heterogeneity issues. To reduce this integration gap, in this paper, we present Java Cá&Lá (JCL), a distributed‐shared‐memory and task‐oriented lightweight middleware for the Java community that separates business logic from distribution issues during the development process and incorporates several requirements that were presented separately in the GPDC middleware literature over the last few decades. JCL allows building distributed or parallel applications with only a few portable API calls, thus reducing the integration problems. Finally, it also runs on different platforms, including small single‐board computers. This work compares and contrasts JCL with other Java middleware systems and reports experimental evaluations of JCL applications in several distinct scenarios.Item GeoCube : representação, computação, e visualização de cubos espaciais.(2012) Rocha, Tárik de Melo e Silva; Lima, Joubert de Castro; Carneiro, Tiago Garcia de Senna; Lisboa Filho, Jugurta; Pereira Junior, Álvaro Rodrigues; Santos, Haroldo GambiniA tecnologia SOLAP (Spatial On-Line Analytical Processing) oferece a junção das funcionalidades OLAP (Online Analytical Processing ) e SIG (Sistema de Informação Geográfica) e abre caminho para uma nova categoria de aplicações que fornecem suporte a manipulação, processamento e navegação em dados espaço-temporais organizados hierarquicamente. Os dados em um sistema OLAP são armazenados como cubos e estes são organizados segundo o conceito de dimensões, medidas e hierarquias. A materialização de um cubo de dados possui ordem de complexidade exponencial em relação ao consumo de memória e tempo de execução. Quando associamos informações espaciais ao cubo, a demanda de memória e processamento aumenta, tornando mais difícil a tarefa de oferecer respostas rápidas ao usuário. Atualmente, poucos trabalhos foram publicados na representação, computação e consulta de cubos espaço-temporais completos. As técnicas apresentadas como materialização seletiva, materialização baseada em aproximações e estruturas para indexação de regiões não oferecem soluções para computação de cubos completos e muitas vezes não podem ser aplicadas para uma grande variedade de funções de agregação espaciais. Arquiteturas de computadores baseadas em endereçamento compartilhado também não são utilizadas nos trabalhos correlatos. Nos trabalhos correlatos as hierarquias são especificadas manualmente por especialistas do domínio e muitas vezes as soluções limitam a quantidade e a variedade de medidas espaciais e não espaciais no cubo. Diante de tal cenário, é proposta uma abordagem para representação, computação e vi consulta de cubos espaço-temporais completos ou parciais, chamada GeoCube. A abordagem GeoCube pode ser executada em máquinas com múltiplos núcleos de processamento. Múltiplas funções de agregação espacial e estatística podem ser combinadas. Também é proposta uma abordagem para formação automática de hierarquias através de regras de vizinhança entre seus objetos espaciais. As regras de vizinhança podem ser definidas pelo usuário e executadas pelo GeoCube. O GeoCube já possui vizinhança nxn, onde n>1. Testes comparativos com um sistema implementado usando PostGIS e vistas materializadas mostram que a GeoCube consegue computar cubos de dados espaciais em até 1/6 do tempo gasto pela tecnologia PostGis em uma máquina com 8 núcleos de processamento.Item GOAL solver : a hybrid local search based solver for high school timetabling.(2016) Fonseca, George Henrique Godim da; Santos, Haroldo Gambini; Toffolo, Túlio Ângelo Machado; Brito, Samuel Souza; Souza, Marcone Jamilson FreitasThis work presents a local search approach to the High School Timetabling Problem. The addressed timetablingmodel is the one stated in the Third International Timetabling Competition (ITC 2011), which considered many instances from educational institutions around the world and attracted seventeen competitors. Our team, named GOAL (Group of Optimization and Algorithms), developed a solver built upon the Kingston High School Timetabling Engine. Several neighborhood structures were developed and used in a hybrid metaheuristic based on Simulated Annealing and Iterated Local Search. The developed algorithm was the winner of the competition and produced the best known solutions for almost all instances.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 Heurísticas baseadas em programação inteira para o problema de escalonamento de múltiplos projetos com múltiplos modos e Restrições de recursos.(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., 2013) Soares, Janniele Aparecida; Santos, Haroldo GambiniO Problema de Escalonamento de Projeto, Project Scheduling Problem (PSP), é tema de diversas pesquisas em ciências da computacão, matemática e pesquisa operacional devido a sua di culdade de resolução e importância prática. O PSP representa problemas de diversas áreas, tais como engenharia de software, engenharia civil, arquitetura de processadores, entre outras. Neste trabalho, é apresentada a versão abrangente do problema conhecida como Escalonamento de Múltiplos Projetos com Múltiplos Modos e Restrição de Recursos. A solução deste problema consiste basicamente em um cronograma de execucão das tarefas dos diversos projetos, de forma que as alocações de recursos renováveis e não renováveis não extrapolem os limites estabelecidos. Para isto, deve-se elencar um modo de execução para cada tarefa, visto que sua duração e a quantidade de recursos consumidos variam de acordo com o modo selecionado. Por fim o cronograma deve também levar em conta restrições de precedência entre as atividades. No presente trabalho são propostas heurísticas de programação inteira para a resolução de um amplo conjunto de instâncias disponibilizadas na competição internacional MISTA2013 -Multidisciplinary International Scheduling Conference. O solver desenvolvido foi um dos vencedores da competição, sendo capaz de encontrar soluções viáveis e competitivas para todas as instânciasItem A hybrid heuristic algorithm for the open-pit-mining operational planning problem.(2010) Souza, Marcone Jamilson Freitas; Coelho, Igor Machado; Ribas, Sabir; Santos, Haroldo Gambini; Merschmann, Luiz Henrique de CamposThis paper deals with the Open-Pit-Mining Operational Planning problem with dynamic truck allocation. The objective is to optimize mineral extraction in the mines by minimizing the number of mining trucks used to meet production goals and quality requirements. According to the literature, this problem is NPhard, so a heuristic strategy is justified. We present a hybrid algorithm that combines characteristics of two metaheuristics: Greedy Randomized Adaptive Search Procedures and General Variable Neighborhood Search. The proposed algorithm was tested using a set of real-data problems and the results were validated by running the CPLEX optimizer with the same data. This solver used a mixed integer programming model also developed in this work. The computational experiments show that the proposed algorithm is very competitive, finding near optimal solutions (with a gap of less than 1%) in most instances, demanding short computing times.Item Integer programming techniques for educational timetabling.(2017) Fonseca, George Henrique Godim da; Santos, Haroldo Gambini; Carrano, Eduardo Gontijo; Stidsen, Thomas Jacob RiisEducational timetabling problems require the assignment of times and resources to events, while sets of required and desirable constraints must be considered. The XHSTT format was adopted in this work because it models the main features of educational timetabling and it is the most used format in recent studies in the field. This work presents new cuts and reformulations for the existing integer programming model for XHSTT. The proposed cuts improved hugely the linear relaxation of the formulation, leading to an average gap reduction of 32%. Applied to XHSTT-2014 instance set, the alternative formulation pro- vided four new best known lower bounds and, used in a matheuristic framework, improved eleven best known solutions. The computational experiments also show that the resulting integer programming mod- els from the proposed formulation are more effectively solved for most of the instances.
- «
- 1 (current)
- 2
- 3
- »