Implementação do Método Criss-Cross para Problemas de Programação Linear de Grande Porte
Autores
|
1988 |
Tibérius de Oliveira e Bonates
|
850,44
|
|
1989 |
850,44
|
Informações:
Publicações do PESC
Implementaçãodo Método Criss-Cross para Problemas de Programação Linear de Grande Porte
Tibérius de Oliveira e Bonates
Junho/2001
| Orientador: | Nelson Maculan Filho | |
| ||
Avaliamos o desempenho de uma classe de algoritmos de pivoteamento para problemas de programação linear: os algoritmos criss-cross. O surgimento destes algoritmos foi motivado pela dificuldade de se encontrar uma base viável para a inicialização dos algoritmos simplex tradicionais. A flexibilidade dos algoritmos criss-cross e sua capacidade de caminhar por vértices inviáveis do problema sugerem a possibilidade de um ganho de performance diante dos algoritmos de pivoteamento clássicos na solução de problemas de grande porte. Implementamos o algoritmo criss-cross original, as variantes finitas que surgiram em seguida e propomos uma modificação nestas variantes, com a qual atingimos bons resultados. Apresentamos os detalhes de nossa implementação, analisamos o comportamento típico dos algoritmos e descrevemos os resultados obtidos na solução de três classes de problemas.
Implementation of the Criss-Cross Method for Solving Large-Scale Linear Programing Problems
Tibérius de Oliveira Bonates
June/2001
| Advisor: | Nelson Maculan Filho | |
| Department: Systems Engineering and Computer Science | ||
We evaluate a class of pivoting algorithms for solving linear programming problems: the criss-cross algorithms. The rise of criss-cross algorithms was motivated by the inherent difficulty of finding a feasible basis for the initialization of traditional simplex algorithms. The flexibility of the criss-cross algorithms and their ability of following a path through possibly infeasible vertices of the problem suggest the possibility of an improvement in the performance of solving large-scale problems compared to the classical pivoting algorithms. We implemented the original criss-cross algorithm and the finite variants that were developed later. We also propose a modification of the finite variants based on the idea of the original algorithm. This modification improved significatively the performance of these variants. We present the details of our implementation, analyze the typical behavior of these algorithms and describe the results achieved in the solution of three classes of problems.