Please use this identifier to cite or link to this item: http://www.repositorio.ufop.br/handle/123456789/4009
Title: pRINS : uma matheurística para problemas binários.
Authors: Gomes, Thiago Macedo
metadata.dc.contributor.advisor: Souza, Marcone Jamilson Freitas
Keywords: Programação heurística
Otimização combinatória
Programação - matemática
Issue Date: 2014
Citation: GOMES, T. M. pRINS : uma matheurística para problemas binários. 2014. 63 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2014.
Abstract: 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.
metadata.dc.description.abstracten: 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.
Description: 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.
URI: http://www.repositorio.ufop.br/handle/123456789/4009
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo autor, 14/11/2014, com as seguintes condições: disponível sob Licença Creative Commons 3.0, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação desta.
Appears in Collections:PPGCC - Mestrado (Dissertações)

Files in This Item:
File Description SizeFormat 
DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf1,04 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons