Browsing by Author "Brito, Samuel Souza"
Now showing 1 - 8 of 8
Results Per Page
Sort Options
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 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 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 Preprocessing and cutting planes with conflict graphs.(2021) Brito, Samuel Souza; Santos, Haroldo GambiniThis paper addresses the development of conflict graph-based algorithms and data structures into the COIN-OR Branch-and-Cut (CBC) solver, including: ð Þi an efficient infrastructure for the construction and manipulation of conflict 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; and ð Þ iv an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities. 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 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 Strong bounds for resource constrained project scheduling : preprocessing and cutting planes.(2020) Araujo, Janniele Aparecida Soares; Santos, Haroldo Gambini; Gendron, Bernard; Jena, Sanjay Dominik; Brito, Samuel Souza; Souza, Danilo SantosResource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known N Phard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. In this paper, we propose a cutting plane algorithm to separate five different cut families, as well as a new preprocessing routine to strengthen resource-related constraints. New lifted versions of the well-known precedence and cover inequalities are employed. At each iteration, a dense conflict graph is built considering feasibility and optimality conditions to separate cliques, odd-holes and strengthened Chvátal-Gomory cuts. The proposed strategies considerably improve the linear relaxation bounds, allowing a state-of-theart mixed-integer linear programming solver to find provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.