Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/259930
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Heuristicas para programação inteira com trajetorias de busca factiveis e infactiveis
Title Alternative: Heuristics for integer programming with feasible and infeasible search trajectories
Author: Takahata, André Kazuo, 1982-
Advisor: Armentano, Vinícius Amaral, 1950-
Abstract: 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.
Subject: Programação inteira
Heurística
Otimização combinatória
Language: Português
Editor: [s.n.]
Date Issue: 2009
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Takahata_AndreKazuo_M.pdf1.09 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.