Browsing by Author "Fonseca, George Henrique Godim da"
Now showing 1 - 11 of 11
Results Per Page
Sort Options
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 A fix-and-optimize heuristic for the ITC2021 sports timetabling problem.(2022) Fonseca, George Henrique Godim da; Toffolo, Túlio Ângelo MachadoThis paper addresses the general and challenging Sports Timetabling Problem proposed during the International Timetabling Competition of 2021 (ITC2021). The problem is expressed in a flexible format which enables modeling a number of real-world constraints that often occur in Sports Timetabling. An integer programming (IP) formulation and a fix-and-optimize heuristic are proposed to address the problem. The fix-and-optimize approach uses the IP formulation to heuristically decompose the problem into sub-problems and efficiently search on very large neighborhoods. The diverse ITC2021 benchmark instances were used to evaluate the proposed methods. The formulation resulted in proven optimal solutions for two instances. However, it failed to produce feasible solutions for most instances. The proposed fix-and-optimize, which uses an automatic sub-problem size calibration strategy, resulted in feasible solutions for 37 out of the 45 ITC2021 instances. Among these solutions, four are the best known in the literature. The proposed approach participated in the ITC2021 and was one of the finalists.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 Heurísticas matemáticas para o problema de escalonamento em máquinas paralelas não relacionadas com tempo de preparo e sequência dependente.(2021) Figueiroa, Guilherme Baumgratz; Toffolo, Túlio Ângelo Machado; Fonseca, George Henrique Godim da; Toffolo, Túlio Ângelo Machado; Fonseca, George Henrique Godim da; Cota, Luciano Perdigão; Penna, Puca Huachi VazO Problema de Sequenciamento em Máquinas Paralelas Não Relacionadas considera um conjunto de tarefas e um conjunto de máquinas homogêneas ou heterogêneas que trabalham em paralelo. Todas as tarefas do conjunto devem ser processadas, sendo necessário escolher em qual máquina cada tarefa será executada. O objetivo é escalonar as tarefas nas máquinas de forma a minimizar o tempo total necessário para executar todas as tarefas, conhecido como makespan, dado pela máquina com maior tempo de processamento. Este trabalho estuda um caso do problema em que as tarefas são independentes, as máquinas heterogêneas e existe um tempo de preparo para execução de cada tarefa, que pode variar dependendo da sequência das tarefas e da máquina. Os principais modelos matemáticos propostos para o problema foram avaliados utilizando o conjunto de instâncias apresentado por Vallada e Ruiz (2011). Dentre os modelos e métodos analisados, o modelo proposto por Avalos-Rosales et al. (2015) e o algoritmo exato proposto por Fanjul-Peyro et al. (2019) obtiveram os melhores resultados tanto em termos de qualidade de solução quanto em termos de tempo de processamento. Assim, com o intuito de abordar instâncias maiores do problema, este trabalho propõe o uso de heurísticas matemáticas Fix-And-Optimize que utilizando os principais modelos disponíveis na literatura. As metodologias propostas consistem em decompor de forma heurística o problema por meio da fixação de um conjunto de tarefas e máquinas. Cada fixação resulta em um subproblema que pode ser resolvido por um modelo matemático ou método exato. Duas variações do algoritmos foram avaliadas, usando os modelos de Avalos-Rosales et al. (2015) e Fanjul-Peyro et al. (2019). Os resultados computacionais mostram que ambos algoritmos propostos obtêm valores próximos do melhor conhecido na literatura. Foram obtidas, ainda, diversas soluções melhores do que a melhor conhecida até então. Dentre as duas abordagens propostas, o algoritmo que utiliza o método de Fanjul-Peyro et al. (2019) para resolver subproblemas obteve os melhores resultados, sendo capaz de obter soluções melhores do que a melhor da literatura para 338 das 1000 instâncias de grande porte consideradas.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.Item Integrating matheuristics and metaheuristics for timetabling.(2016) Fonseca, George Henrique Godim da; Santos, Haroldo Gambini; Carrano, Eduardo GontijoThe High School Timetabling Problem requires the assignment of times and resources to events, while sets of required and desirable constraints must be considered. The most common approach for this problem is to employ metaheuristic methods. This work presents a matheuristic approach that combines a Variable Neighbourhood Search algorithm with mathematical programming-based neighbourhoods for high school timetabling. Computational experiments on well-known benchmark instances demonstrate the success of the proposed hybrid approach, which outperforms the standalone Variable Neighbour- hood Search algorithm by far. Additionally, the proposed algorithm was able to improve 15 out of 17 current best known solutions in a very famous benchmark set.Item Late acceptance hill-climbing for high school timetabling.(2016) Fonseca, George Henrique Godim da; Santos, Haroldo Gambini; Carrano, Eduardo GontijoThe application of the Late Acceptance HillClimbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.Item Métodos de busca heurística para problemas de programação de horários modelados em XHSTT.(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) Fonseca, George Henrique Godim da; Santos, Haroldo GambiniO Problema da Programação de Horários Escolares é alvo de diversas pesquisas em Pesquisa Operacional e Inteligência Artificial devido a sua dificuldade de resolução e import^ancia prática. Uma solução para esse problema consiste basicamente na alocação de aulas a horários e na alocação dos recursos para essas aulas. Essa alocação deve atender a várias restrições especificadas a priori. O presente trabalho considera a solução do problema proposto pela Third Interntional Timetabling Competition (ITC2011), a qual inclui um amplo conjunto de inst^ancias originadas de diversas instituições educacionais ao redor do mundo. O presente trabalho prop~oe diversas técnicas de busca local para solucionar o problema. O formato de especificação de inst^ancias considerado foi o XHSTT, permitindo que qualquer inst^ancia especificada no referido formato possa ser manipulada pelos algoritmos propostos. Uma característica estrutural importante da nossa abordagem é o uso da plataforma KHE para gerar soluções iniciais, combinada com uma abordagem de busca multi-vizinhança. Os resultados obtidos incluem o desenvolvimento do algoritmo vencedor da competição. Fomos ainda capazes de encontrar soluções factíveis para treze de dezoito inst^ancias e melhorar quinze de dezesseis melhores soluções conhecidasItem Problema de programação de horários de cursos universitários da ITC2019 : modelos e algoritmos.(2022) Santos, Paulo Sérvulo; Fonseca, George Henrique Godim da; Oliveira, Paganini Barcellos de; Fonseca, George Henrique Godim da; Oliveira, Paganini Barcellos de; Santos, Haroldo Gambini; Toffolo, Túlio Ângelo MachadoEste trabalho aborda o Problema de Agendamento de Horários de Cursos Universitários apresentado na Competição Internacional de Horários 2019 (ITC2019). O problema é composto por um conjunto de cursos, salas e estudantes, onde cada curso possui uma estrutura hierárquica que define em quais turmas o aluno pode se matricular. O objetivo é alocar uma sala e um horário para cada turma e alocar os alunos às turmas de forma a não violar as restrições de distribuição rígidas e minimizar os custos associados aos tempos, salas, penalidades das restrições fracas e conflitos de alunos. Para solucionar a problemática, uma heurística matemática multi-vizinhança do tipo Fixa-e-Otimiza, que utiliza um modelo já disponível na literatura, foi proposta. Além da heurística matemática, foram propostas diferentes técnicas de pré-processamento para a redução da dimensão das instâncias, o que contribui para compactação dos modelos. Também foi desenvolvida uma heurística construtiva capaz de gerar soluções válidas que são usadas como entrada para o algoritmo Fixa-e-Otimiza. Os resultados computacionais indicam que, para algumas das instâncias, as estratégias de pré-processamento auxiliam na geração de um modelo mais compacto. Obteve-se uma redução média de 22,03% e 7,65% na quantidade de variáveis e restrições, respectivamente, quando comparados com trabalhos da literatura. O algoritmo Fixa-e-Otimiza também se mostrou eficiente na medida em que obteve alguns resultados melhores que o segundo e terceiro colocados da ITC2019. Mesmo com o grande esforço no pré-processamento para reduzir a dimensão das instâncias, algumas delas não puderam ser carregadas em memória para serem resolvidas pelo modelo matemático.Item A SA-VNS approach for the high school timetabling problem.(2012) Brito, Samuel Souza; Fonseca, George Henrique Godim da; Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Souza, Marcone Jamilson FreitasThe High School Timetabling Problem consists in assigning timeslots and resources to events, satisfying constraints which heavily depend on the specific institution. This work deals with the problem of the ongoing III International Timetabling Competition (ITC), which includes a diverse set of instances from many educational institutions around the world. We proposed an approach based on Simulated Annealing and Variable Neighborhood Search metaheuristics. One important structural feature of our approach is the use of the Kingston’s High School Timetabling Engine (KHE) to generate initial solutions combined with the multi-neighborhood search. Such approach led us to the finals of the ongoing competition.Item Variable Neighborhood Search based algorithms for high school timetabling.(2014) Fonseca, George Henrique Godim da; Santos, Haroldo GambiniThis work presents the application of Variable Neighborhood Search (VNS) based algorithms to the High School Timetabling Problem. The addressed model of the problem was proposed by the Third International Timetabling Competition (ITC2011), which released many instances from educational institutions around the world and attracted 17 competitors. Some of the VNS algorithm variants were able to outperform the winner of Third I T C solver, which proposed a Simulated Annealing – Iterated local Search approach. This result coupled with another reports in the literature points that VNS based algorithms are a practical solution method for providing high quality solutions for some hard timetabling problems. Moreover they are easy to implement with few parameters to adjust.