Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T19:39:00Z (GMT). No. of bitstreams: 1
Takahata_AndreKazuo_M.pdf: 1113954 bytes, checksum: 18f4c96c943dced30f100b8a56c97258 (MD5)
Previous issue date: 2009 / Resumo: Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação
linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são
conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção
de soluções de alta qualidade em tempo reduzido.
As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de
um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em
trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este
enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para
problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas
e apresenta resultados de testes em instâncias da literatura. / Abstract: In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to
combine the flexibility offered by heuristics and the expressive advances achieved in the
development of optimization solvers so as to obtain high quality solutions in a short time.
The proposed heuristics are based on rounding solutions located on the rays of a cone
whose vertex is associated with the optimal solution of the linear programming relaxation, and in
feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is
motivated by its geometric appeal and by the success of similar approaches in heuristics for
solving combinatorial problems. This work describes the development and implementation of the
heuristics and presents computational tests on instances from literature. / Mestrado / Automação / Mestre em Engenharia Elétrica
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/259930 |
| Date | 05 August 2009 |
| Creators | Takahata, André Kazuo, 1982- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Armentano, Vinícius Amaral, 1950-, Senne, Edson Luiz França, Souza, Cid Carvalho de |
| Publisher | [s.n.], Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e de Computação, Programa de Pós-Graduação em Engenharia Elétrica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 151 p. : il., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds