Dual simplex type methods to two-bounded linear optimization problems

Author(s)

Ricardo Silveira Sousa

• Document type: Doctoral Thesis
• 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: 2005-09-30

Examining board members

Marcos Nereu Arenales; Geraldo Roberto Martins da Costa; Aurelio Ribeiro Leite de Oliveira; José Mario Martinez Perez; Geraldo Nunes Silva

• Advisor: Marcos Nereu Arenales

Abstract

Linear optmization has been studied in-depth since 1947, when George Dantizg published lhe Simplex method. From 1984. research on linear optmization was enormously intensiíled because of the publication of the Interior Point method by Narendra Karmarkar, which showed to be computationally effieient for many large and sparse problems, and with polynomial time complexity. Although many variants of the Simplex method do not have polynomial time complexity, they perform well for a number of practical problems, presenting polynomial behaviour, and this constitutes a folklore of Simplex typc methods. Recently, the interest in the efficiency of Simplex methods has increased. There is an underlying question, which is perhaps the biggest challenge nowadays in the Optimization theory: \' i s it possible to build a time polynomial simplex tvpe algorithm, which is effieient from the computational point of view?\" The answer to this question is certainly not trivial, and probably it is negative. One is faced with the hard task of investigating the complexity, one by one, of the proposed methods. In this vvork, we study the most used version of the simplex method: the Dual Simplex method, specialized for the general form (two sided constraints), whose dual is a linear piecewise optimization problem. The importance of the general form is not only because it can easily deal with other forms, but many important practical problems arise naturally in this way, and pre-processing techniques of tighting bounds lead to this form. The following aspeets were investigated: different piecewise linear line searching, the effect of stalling phenomena due to degenerate solutions and how anti-cyclic rules can inlluence it positivelv, the steepest edge rule, and some techniques to handle imbedded linear systems, including the iterativo bi-conjugated gradient method, in which an expectation arises to improve the computational performance for very large and sparse problems. (AU)