Sparse two-bounded linear optImization problems

Author(s)

Carla Taviane Lucke da Silva Ghidini

• 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: 2002-12-17

Examining board members

Marcos Nereu Arenales; Ernesto Julian Goldberg Birgin; Luis Gustavo Nonato

• Advisor: Marcos Nereu Arenales
• Field of knowledge: Engineering - Production Engineering
• Indexed in: Banco de Dados Bibliográficos da USP-DEDALUS
• Location: Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação. Biblioteca Prof. Achille Bassi; ICMSC /T; S586po

Abstract

Linear optimization has been studied since 1947 when the simplex method was published by George Dantzig, and ií is still successlully used in practice. A number of varianls to the simplex method have been proposed trying to obtain better efficiency. In addition, various implementations have been proposed to deal with large scale problems. Two-side constraints and sparse linear optimization problems, the main object of this work, are of great interest in practice, since they represent a number of real problems, such as, production planning problems. mix problems and others. This work presents a simplex-typed method, named two-side constraint dual simplex method with piecewise linear search. This method was implemented together with some heuristics to handle sparsity and run to solve a set of linear optimization problems in order to analyse their computational performance. (AU)