Effective implementations of simplex type methods for solving linear programming problems

• Grant number: 07/01791-0
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2008
• End date: February 28, 2009
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marcos Nereu Arenales
• Grantee: Pedro Augusto Munari Junior
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated research grant: 06/03496-3 - Theory and practice of cutting and packing problems, AP.TEM

Abstract

A otimização linear tem sido objeto de estudo há mais de 50 anos, desde os trabalhos pioneiros de George B. Dantzig em 1947. O grande interesse por esta área decorre da capacidade em modelar problemas reais e complexos presentes em diversas outras áreas, e devido aos diversos algoritmos eficientes propostos na literatura para a resolução desses problemas. Além disso, a otimização linear é fundamental na resolução de problemas de otimização inteira, cujos algoritmos dependem da resolução de vários problemas de otimização linear. Os métodos mais utilizados para a resolução de problemas de otimização linear são os métodos tipo simplex. A implementação computacional direta desses métodos, exatamente como são descritos na teoria e sem uma abordagem adequada, leva inevitavelmente a resultados indesejáveis para a resolução de problemas de grande porte. O desenvolvimento de softwares científicos de otimização que sejam capazes de resolver problemas reais, complexos e de grande porte exige o conhecimento da teoria de otimização, dos resultados relevantes da computação científica, de princípios de engenharia de software e do estado-da-arte em tecnologia de hardware computacional. Os objetivos deste projeto são o estudo da teoria de métodos tipo simplex, em especial métodos tipo dual-simplex, e das abordagens computacionais adequadas para a implementação eficiente desses métodos. Além disso, como resultado dos estudos e das implementações realizadas, pretende-se produzir um software científico para a resolução eficiente de problemas de otimização linear de grande porte. (AU)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

MUNARI JUNIOR, Pedro Augusto. Computational techniques for an efficient and stable implemantation of simplex-type methods. 2009. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.