Heuristicas para programação inteira com trajetorias de busca factiveis e infactiveis
Andre Kazuo Takahata
DISSERTAÇÃO
Português
T/UNICAMP T139h
[Heuristics for integer programming with feasible and infeasible search trajectories]
Campinas, SP : [s.n.], 2009.
151 p. : il.
Orientador: Vinicius Amaral Armentano
Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
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... Ver mais 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.
Ver menos
linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são
conjugados a... Ver mais 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.
Ver menos
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... Ver mais 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.
Ver menos
combine the flexibility... Ver mais 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.
Ver menos
Heuristicas para programação inteira com trajetorias de busca factiveis e infactiveis
Andre Kazuo Takahata
Heuristicas para programação inteira com trajetorias de busca factiveis e infactiveis
Andre Kazuo Takahata
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra