Theoretical and computational issues for improving the performance of linear optimization methods (2013)
- Authors:
- Autor USP: MUNARI JUNIOR, PEDRO AUGUSTO - ICMC
- Unidade: ICMC
- Sigla do Departamento: SME
- Subjects: MÉTODOS DE PONTOS INTERIORES; PESQUISA OPERACIONAL; OTIMIZAÇÃO MATEMÁTICA
- Keywords: Branch-and-price; Branch-and-price; Columm generation; Geração de colunas; Interior point methods; Linear optimization; Métodos tipo simplex; Otimização linear; Simplex type methods
- Language: Inglês
- Abstract: Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eficiente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que émais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem serexploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura
- Imprenta:
- Publisher place: São Carlos
- Date published: 2013
- Data da defesa: 31.01.2013
-
ABNT
MUNARI JUNIOR, Pedro Augusto. Theoretical and computational issues for improving the performance of linear optimization methods. 2013. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2013. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/. Acesso em: 25 abr. 2024. -
APA
Munari Junior, P. A. (2013). Theoretical and computational issues for improving the performance of linear optimization methods (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/ -
NLM
Munari Junior PA. Theoretical and computational issues for improving the performance of linear optimization methods [Internet]. 2013 ;[citado 2024 abr. 25 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/ -
Vancouver
Munari Junior PA. Theoretical and computational issues for improving the performance of linear optimization methods [Internet]. 2013 ;[citado 2024 abr. 25 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
