Full text
| |
| Author(s): |
Pedro Augusto Munari Junior
Total Authors: 1
|
| 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: | 2013-01-31 |
| Examining board members: |
Marcos Nereu Arenales;
Marcus Vinicius Soledade Poggi de Aragão;
José Manuel Vasconcelos Valério de Carvalho;
Aurelio Ribeiro Leite de Oliveira;
Maristela Oliveira dos Santos
|
| Advisor: | Marcos Nereu Arenales; Jacek Gondzio |
| Abstract | |
Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature (AU) | |
| FAPESP's process: | 08/09040-7 - Theoretical and computational issues for the efficient implementation of linear optimization methods |
| Grantee: | Pedro Augusto Munari Junior |
| Support Opportunities: | Scholarships in Brazil - Doctorate |