Implementação paralela escalável e eficiente do algoritmo simplex padrão em arquitetura multicore

Este trabalho apresenta uma implementação paralela escalável e eficiente do algoritmo Simplex padrão em arquitetura de processadores multicore para resolver problemas de programação linear de grande escala. Apresenta-se um esquema geral explicando como foi paralelizado cada passo do algoritmo simplex padrão, apontando pontos importantes da implementação paralela. Foram realizadas análises de desempenho através da comparação dos tempos sequenciais utilizando o Simplex tableau e Simplex do CPLEXR da IBM. Os experimentos foram realizados em uma máquina de memória compartilhada com 24 núcleos. A análise de escalabilidade foi feita com problemas de diferentes dimensões, encontrando evidências de que a implementação paralela proposta do algoritmo simplex padrão tem melhor eficiência paralela para problemas com mais variáveis do que restrições. Na comparação com CPLEXR , o algoritmo proposto paralelo obteve uma eficiência de até 16 vezes maiorThis work presents a scalable and efficient parallel implementation of the Standard Simplex algorithm in the multicore architecture to solve large scale linear programming problems. We present a general scheme explaining how each step of the standard Simplex algorithm was parallelized, indicating some important points of the parallel implementation. Performance analysis were conducted by comparing the sequential time using the Simplex tableau and the Simplex of the CPLEXR IBM. The experiments were executed on a shared memory machine with 24 cores. The scalability analysis was performed with problems of different dimensions, finding evidence that our parallel standard Simplex algorithm has a better parallel efficiency for problems with more variables than constraints. In comparison with CPLEXR , the proposed parallel algorithm achieved a efficiency of up to 16 times bette