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. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-11-20T16:36:46Z
No. of bitstreams: 2
license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5)
DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-20T16:39:12Z (GMT) No. of bitstreams: 2
license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5)
DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Made available in DSpace on 2014-11-20T16:39:12Z (GMT). No. of bitstreams: 2
license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5)
DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5)
Previous issue date: 2014 / 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. ______________________________________________________________________________________________ / ABSTRACT: 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:localhost:123456789/4009 |
| Date | January 2014 |
| Creators | Gomes, Thiago Macedo |
| Contributors | Souza, Marcone Jamilson Freitas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFOP, instname:Universidade Federal de Ouro Preto, instacron:UFOP |
| Rights | 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., info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds