Computational techniques for an efficient and stable implemantation of simplex-type methods

Author(s)

Pedro Augusto Munari Junior

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2009-03-06

Examining board members

Marcos Nereu Arenales; Francisco de Assis Magalhães Gomes Neto; Franklina Maria Bragion de Toledo

• Advisor: Marcos Nereu Arenales

Abstract

Simplex-type methods are the basis of the main linear optimization solvers. The straightforward implementation of these methods as they are presented in theory yield unexpected results in solving reallife large-scale problems. Hence, it is essencial to use suitable computational techniques for an efficient and stable implementation. In this thesis, we address the main techniques focusing on those which aim for numerical stability of the method: use of tolerances, stable ratio test, scaling and representation of the basis matrix. For the latter topic, we present two techniques, the Product Form of Inverse and the LU decomposition. The Netlib problems are solved using the approaches addressed and the results are analyzed (AU)

• FAPESP's process: 07/01791-0 - Effective implementations of simplex type methods for solving linear programming problems
• Grantee: Pedro Augusto Munari Junior
• Support Opportunities: Scholarships in Brazil - Master