Exportar registro bibliográfico

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:
  • Data da defesa: 31.01.2013
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      MUNARI JUNIOR, Pedro Augusto; ARENALES, Marcos Nereu; GONDZIO, Jacek. Theoretical and computational issues for improving the performance of linear optimization methods. 2013.Universidade de São Paulo, São Carlos, 2013. Disponível em: < http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/ >.
    • APA

      Munari Junior, P. A., Arenales, M. N., & Gondzio, J. (2013). Theoretical and computational issues for improving the performance of linear optimization methods. 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, Arenales MN, Gondzio J. Theoretical and computational issues for improving the performance of linear optimization methods [Internet]. 2013 ;Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/
    • Vancouver

      Munari Junior PA, Arenales MN, Gondzio J. Theoretical and computational issues for improving the performance of linear optimization methods [Internet]. 2013 ;Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16042013-101426/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021