Banca de QUALIFICAÇÃO: DEMETRIOS ARAUJO MAGALHAES COUTINHO

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: DEMETRIOS ARAUJO MAGALHAES COUTINHO
DATA: 28/01/2013
HORA: 14:00
LOCAL: Sala 2 - DCA
TÍTULO:

O efeito da dualidade em programação linear na escalabilidade paralela do algoritmo simplex

PALAVRAS-CHAVES:

Escalabilidade Paralela, Algoritmo Simplex, Era Multicore, Programação Linear, dualidade

PÁGINAS: 37
GRANDE ÁREA: Engenharias
ÁREA: Engenharia Elétrica
RESUMO:

O objetivo deste trabalho é analisar a escalabilidade paralela do
algoritmo Simplex e encontrar evidências que mostrem que, na era
multicore, pode ser mais viável resolver problemas de Programação Linear
(PL) duais ou primais dependendo do volume de dados. Programação Linear
consiste em determinar o custo máximo ou mínimo de um problema matemático
modelado com equações e inequações lineares. Um dos conceitos mais
importantes em programação linear é a dualidade. Qualquer problema de PL
tem associado outro problema de PL, chamado dual. Nesse contexto, o
problema original denomina-se por primal. Para resolver tais problemas,
existem alguns métodos de resolução como, pontos interiores, Simplex
padrão e revisado. Todavia, o Simplex é tido como o método mais eficiente
de solução para problemas lineares, tais como, métodos de decomposição,
programação inteira e outras classes de problemas ligadas à programação
linear. Desde a década de 70, existem estudos de paralelização do método
padrão do Simplex. Contudo, não existem muitos trabalhos atuais de
paralelização em arquiteturas de memória compartilhada, como é comum hoje
em computadores pessoais. A fabricação de processadores com frequência
elevada tornou-se mais difícil devido ao aumento exponencial de
temperatura e, consequentemente, ao grande consumo de energia. A solução
encontrada pela indústria, e usada hoje, foi a produção de chips
multiprocessados, ou seja, processadores com vários núcleos. A tendência é
que novas gerações de processadores tenham mais e mais núcleos ao invés de
frequências maiores. Isso torna necessário o uso de peralelismo para fazer
uso eficiente desses novos processadores. Este estudo mostra que, devido
ao teorema da dualidade, pode ser mais eficiente resolver um problema de
PL na sua forma dual ao invés da primal, ou visse versa. Os resultados
mostram que, apesar de haver vantagens no uso de um em relacão ao outro
dependendo da quantidade de variáveis e restrições, ambos os casos
apresentam boa escalabilidade para o aumento to tamanho do problema.

MEMBROS DA BANCA:
Presidente - 350241 - JORGE DANTAS DE MELO
Interno - 1746084 - DANIEL ALOISE
Interno - 1673543 - SAMUEL XAVIER DE SOUZA