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

• Ano de defesa: 2014
• Autor(a) principal: Coutinho, Demetrios Araújo Magalhães
• Orientador(a): Souza, Samuel Xavier de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio Grande do Norte
• Programa de Pós-Graduação: Programa de Pós-Graduação em Engenharia Elétrica
• Departamento: Automação e Sistemas; Engenharia de Computação; Telecomunicações
• País: BR
• Palavras-chave em Português: Simplex. CPLEXR. Eficiência Paralela. Escalabilidade Paralela. Programação Linear
• Palavras-chave em Inglês: Simplex. CPLEXR. Parallel Efficiency. Parallel Scalability. Linear Programming
• Área do conhecimento CNPq: CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL::PROGRAMACAO LINEAR, NAO-LINEAR, MISTA E DINAMICA
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/15502

This 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 better