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

Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca NetlibSimplex-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 analyze